题目
题目链接
题目大意：给出一棵 $n$ 个点的树，边有边权，求出 $\sum (w_{u, v} \times |siz_u - siz_v|)$。$1 \le n \le 10^6$。
思路
考虑一条边连接的两个点，设 $u$ 为父亲结点，$v$ 为子结点，这条边一端的结点数为 $siz_v$。
自然另一边的结点数就为 $n - siz_v$。
只需要一遍 dfs 就可以求出答案。
注意开 long long。
代码
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}
typedef unsigned long long uLL;
typedef long long LL;
struct Edge {
int to;
LL dis;
} ;
std::vector<Edge> g[1000010];
LL siz[1000010];
LL ans;
int n;
LL labs(LL a, LL b) { return a - b > 0 ? a - b : b - a; }
void dfs(int x, int p) {
siz[x] = 1;
for (auto i : g[x]) {
if (i.to != p) {
dfs(i.to, x);
siz[x] += siz[i.to];
ans += i.dis * labs(siz[i.to], (n - siz[i.to]));
}
}
}
int main() {
read(n);
for (int i = 1, u, v, w; i < n; ++i) {
read(u), read(v), read(w);
g[u].push_back((Edge){v, w}), g[v].push_back((Edge){u, w});
}
dfs(1, 0);
printf("%lld\n", ans);
return 0;
}
|