题目的意思就是给定一张有根图，根据所给规则计算费用之和。这题有点像bzoj1131，但更简单，因为不用换根。
我们可以假定以1为根，计算出以i为根节点的子树的节点数son[i]。统计时对于边(u,v)，假设u为以1为根的树中v的父亲（反过来也一样），那么费用就要加上son[v]+(n-son[v])。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| /**************************************************************
Problem: 2435
User: abcdabcd987
Language: C++
Result: Accepted
Time:6944 ms
Memory:49116 kb
****************************************************************/
#include <cstdlib>
#include <iostream>
using namespace std;
struct link {
int v,next;
} g[3000000];
int q[1000001],son[1000001],father[1000001],n,top,root,a[1000000][3];
bool s[1000001];
long long ans;
inline void join(const int x,const int y) {
g[++top].v=y;
g[top].next=g[x].next;
g[x].next=top;
}
void bfs(const int source) {
int head=0,tail=1;
q[tail]=source;
s[source]=true;
father[source]=-1;
while (head<tail) {
int u=q[++head],v=g[u].next;
son[u]=1;
while (v!=-1) {
if (!s[g[v].v]) {
s[g[v].v]=true;
father[g[v].v]=u;
q[++tail]=g[v].v;
}
v=g[v].next;
}
}
for (int i=n;i>1;--i) son[father[q[i]]]+=son[q[i]];
}
int main() {
ios::sync_with_stdio(false);
cin>>n;
for (int i=1;i<=n;++i) g[i].next=-1;
top=n;
for (int i=1;i<n;++i) {
cin>>a[i][0]>>a[i][1]>>a[i][2];
join(a[i][0],a[i][1]);
join(a[i][1],a[i][0]);
}
bfs(1);
for (int i=1;i<n;++i) {
int k=father[a[i][0]]==a[i][1]?a[i][0]:a[i][1];
ans+=static_cast<long long>(abs(son[k]-(n-son[k])))*a[i][2];
}
cout<<ans;
}
|
