*[hackerrank]Cut the tree-白红宇

*[hackerrank]Cut the tree

阅读量：4542 次

发布时间：2019-06-08

本文共 1059 字，大约阅读时间需要 3 分钟。

https://www.hackerrank.com/contests/w2/challenges/cut-the-tree

树分成两部分，求两部分差最小。一开始想多了，后来其实求一下总和，求一下分部的和就行了。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;vector
          
           
            > tree;vector
            
              visited;vector
             
               val;int totalVal;int subSum(int root, int& minCut) { int sum = 0; visited[root] = true; for (int i = 0; i < tree[root].size(); i++) { int sub = tree[root][i]; if (visited[sub]) continue; int x = subSum(sub, minCut); sum += x; } sum += val[root]; minCut = min(minCut, abs(totalVal - 2 * sum)); return sum;}int main() { int N; cin >> N; tree.resize(N + 1); visited.resize(N + 1); val.resize(N + 1); totalVal = 0; for (int i = 1; i <= N; i++) { cin >> val[i]; totalVal += val[i]; } for (int i = 0; i < N - 1; i++) { int a, b; cin >> a >> b; tree[a].push_back(b); tree[b].push_back(a); } int minCut = INT_MAX; // pick 1 as root subSum(1, minCut); cout << minCut << endl; return 0;}