恩，直接DFS，注意用long long int，我就是开始没用long long int，结果错了几次。
思路：
先找一个节点DFS，把树变成有根树，然后统计每个节点的子孙和自己一共有多少牛，记为cow[节点编号]，一共有多少牛，记为total_cow，以及全部牛到这个叶子节点所需的花费，记为cost[节点编号]。
然后再DFS，还是从先前找的的叶子开始。
当搜到root时cost[children of root]=cost[root]+(cow_total-cow[children of root])*length(from root to children of root)-cow[children of root])*length(from root to children of root)。
解释：cost[root]是到当前节点集合的费用，如果到孩子那里去集合，那么就要把从孩子哪儿赶来的牛赶回去，所以-cow[children of root])*length(from root to children of root)，然后还要把不是在孩子及其子孙那里的牛赶过来，所以+(cow_total-cow[children of root])*length(from root to children of root)。
CO
/*
PROG: gather
LANG: C++
ID: boleyn.2
*/
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2010-4-23
DESCRIPTION:
TITLE: Great Cow Gathering [Jeffrey Wang from a contest, 2010]
CONTENT:
Bessie is planning the annual Great Cow Gathering for cows all
across the country and, of course, she would like to choose the
most convenient location for the gathering to take place.
Each cow lives in on
(conveniently numbered 1..N) which are connected by N-1 roads in
such a way that it is possible to get from any barn to any other
barn via the roads. Road i connects barns A_i and B_i (1 <= A_i <=
N; 1 <= B_i <= N) and has length L_i (1 <= L_i <= 1,000). The Great
Cow Gathering can be held at any on
barn i has C_i (0 <= C_i <= 1,000) cows living in it.
When choosing the barn in which to hold the Cow Gathering, Bessie
wishes to maximize the convenience (which is to say minimize the
inconvenience) of the chosen location. The inconvenience of choosing
barn X for the gathering is the sum of the distances all of the
cows need to travel to reach barn X (i.e., if the distance from
barn i to barn X is 20, then the travel distance is C_i*20). Help
Bessie choose the most convenient location for the Great Cow
Gathering.
Consider a country with five barns with [various capacities] connected
by various roads of varying lengths. In this set of barns, neither
barn 3 nor barn 4 houses any cows.
1 3 4 5
@–1–@–3–@–3–@[2]
[1] |
2
|
@[1]
2
Bessie can hold the Gathering in any of five barns; here is the
table of inconveniences calculated for each possible location:
Gather —– Inconvenience ——
Location B1 B2 B3 B4 B5 Total
1 0 3 0 0 14 17
2 3 0 0 0 16 19
3 1 2 0 0 12 15
4 4 5 0 0 6 15
5 7 8 0 0 0 15
If Bessie holds the gathering in barn 1, then the inconveniences
from each barn are:
Barn 1 0 — no travel time there!
Barn 2 3 — total travel distance is 2+1=3 x 1 cow = 3
Barn 3 0 — no cows there!
Barn 4 0 — no cows there!
Barn 5 14 — total travel distance is 3+3+1=7 x 2 cows = 14
So the total inconvenience is 17.
The best possible convenience is 15, achievable at by holding the
Gathering at barns 3, 4, or 5.
PROBLEM NAME: gather
INPUT FORMAT:
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains a single integer: C_i
* Lines N+2..2*N: Line i+N+1 contains three integers: A_i, B_i, and
L_i
SAMPLE INPUT (file gather.in):
5
1
1
0
0
2
1 3 1
2 3 2
3 4 3
4 5 3
OUTPUT FORMAT:
* Line 1: The minimum inconvenience possible
SAMPLE OUTPUT (file gather.out):
15
*/
#include <stdio.h>
#include <vector>
using std::vector;
const long long int oo=1000000000000000000ll;
const int MAXN=100000;
int N;
long long int C[MAXN+1];
long long int A[MAXN-1],B[MAXN-1],L[MAXN-1];
vector<long long int> children[MAXN+1],length[MAXN+1];
long long int total_cow;
long long int cow[MAXN+1];
long long int cost[MAXN+1];
long long int answer;
void prepare(int root,int father_of_root=0)
{
total_cow+=C[root];
cow[root]+=C[root];
for (int i=0;i<children[root].size();i++)
if (children[root][i]!=father_of_root)
{
prepare(children[root][i],root);
cow[root]+=cow[children[root][i]];
cost[root]+=cost[children[root][i]]
+cow[children[root][i]]*length[root][i];
}
//printf(“cost and cow of %d : %d %d\n”,root,cost[root],cow[root]);
}
void get_answer(int root,int father_of_root=0)
{
//printf(“cost of %d: %d\n”,root,cost[root]);
if (cost[root]<answer) answer=cost[root];
for (int i=0;i<children[root].size();i++)
if (children[root][i]!=father_of_root)
{
cost[children[root][i]]=cost[root]
+(total_cow-cow[children[root][i]]*2)
*length[root][i];
get_answer(children[root][i],root);
}
}
void print(long long int long_long_int)
{
if (long_long_int>=10)
print(long_long_int/10);
printf(“%d”,int(long_long_int%10));
}
int main()
{
freopen(“gather.in”,“r”,stdin);
freopen(“gather.out”,“w”,stdout);
scanf(“%d\n”,&N);
for (int i=1;i<=N;i++)
scanf(“%d\n”,&C[i]);
for (int i=0;i<N-1;i++)
scanf(“%d %d %d\n”,&A[i],&B[i],&L[i]);
for (int i=0;i<N-1;i++)
{
children[A[i]].push_back(B[i]);
children[B[i]].push_back(A[i]);
length[A[i]].push_back(L[i]);
length[B[i]].push_back(L[i]);
}
int leaf;
for (int i=1;i<=N;i++)
if (children[i].size()==1)
{
leaf=i;
break;
}
prepare(leaf);
answer=oo;
get_answer(leaf);
/*
printf(“%lld\n”,answer); //for Linux/Unix
printf(“%I64d\n”,answer); //for Windows
*/
//for anywhere
print(answer);
printf(“\n”);
fclose(stdin);
fclose(stdout);
return 0;
}