Cut the tree : Challenge | Weekly Challenges - Week 2 | HackerRank
Atul is into graph theory, and he is learning about trees nowadays. He observed that the removal of an edge from a given tree T will result in the formation of two separate trees, T1 and T2.
Each vertex of the tree T is assigned a positive integer. Your task is to remove an edge, such that the Tree_diff of the resultant trees is minimized. Tree_diff is defined as the following:
http://www.cnblogs.com/sunshineatnoon/p/3914990.html
Total sum and sum of node.
int value[100001], n, tot, best;
vector<vector<int> > v;
bool visited[100001];
int sum[100001];
int dfs(int node)
{
int ret = 0;
visited[node] = true;
int sz = (int)v[node].size();
for (int i = 0; i < sz; i++)
{
int next = v[node][i];
if (!visited[next])
ret += dfs(next);
}
return sum[node] = value[node] + ret;
}
int main()
{
best = INT_MAX;
tot = 0;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> value[i];
tot += value[i];
}
v.resize(n + 1);
for (int i = 0; i < n - 1; i++)
{
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1);
for (int i = 1; i <= n; i++)
if (abs(tot - sum[i] - sum[i]) < best)
best = abs(tot - sum[i] - sum[i]);
cout << best << endl;
return 0;
}
https://www.hackerrank.com/contests/w2/challenges/cut-the-tree/editorial
Read full article from Cut the tree : Challenge | Weekly Challenges - Week 2 | HackerRank
Atul is into graph theory, and he is learning about trees nowadays. He observed that the removal of an edge from a given tree T will result in the formation of two separate trees, T1 and T2.
Each vertex of the tree T is assigned a positive integer. Your task is to remove an edge, such that the Tree_diff of the resultant trees is minimized. Tree_diff is defined as the following:
F(T) = Sum of numbers written on each vertex of a tree T Tree_diff(T) = abs(F(T1) - F(T2))http://www.cnblogs.com/sunshineatnoon/p/3914990.html
然后从树的任意一个节点开始dfs，把它的value值依次加上各个child为root的子树节点值，就得到以它为root的子树的节点值得和了。而它的child为root的子树节点和就用递归的方法求。上面说了，每次读入一条边(a,b)的时候，即把b加入到a的children集合里面，也把a加入到b的children集合里面。那么在dfs的时候，怎么知道谁是父节点，谁是子节点呢？就用一个visited数组，因为在dfs过程中，父节点一定先被访问，所以在一个节点的children集合里面，已经被visited过的节点就不是它的子节点了。
-- we can use post-order to get sum of node, so we don't need to use visited array.Total sum and sum of node.
int value[100001], n, tot, best;
vector<vector<int> > v;
bool visited[100001];
int sum[100001];
int dfs(int node)
{
int ret = 0;
visited[node] = true;
int sz = (int)v[node].size();
for (int i = 0; i < sz; i++)
{
int next = v[node][i];
if (!visited[next])
ret += dfs(next);
}
return sum[node] = value[node] + ret;
}
int main()
{
best = INT_MAX;
tot = 0;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> value[i];
tot += value[i];
}
v.resize(n + 1);
for (int i = 0; i < n - 1; i++)
{
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1);
for (int i = 1; i <= n; i++)
if (abs(tot - sum[i] - sum[i]) < best)
best = abs(tot - sum[i] - sum[i]);
cout << best << endl;
return 0;
}
https://www.hackerrank.com/contests/w2/challenges/cut-the-tree/editorial
Read full article from Cut the tree : Challenge | Weekly Challenges - Week 2 | HackerRank
