题目描述
Link
Solution
考虑使用换根法。
在每次换根的时候，有些节点的深度+1，而另外一些的节点深度就会-1。
所以，换根的方程为 f[to] = d[to] - size[to] - 1 +（f[u] - d[to] + 1 + (n - size[to]))，其中 d 为每个子树里的所有节点的深度之和，size 为子数大小。
简化一下：f[to] = f[u] - 2 * size[to] + n
Code
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
#define MAXN 1000010
struct Edge {
int v, nx;
}e[MAXN << 1];
int head[MAXN], ecnt, n, m, x, y, dep[MAXN], f[MAXN], siz[MAXN], d[MAXN], ans, l;
void add(int f, int t) {
e[++ecnt] = (Edge) {t, head[f]};
head[f] = ecnt;
}
void dfs(int fa, int u, int dp) {
siz[u] = 1;
dep[u] = dp;
d[u] = dp;
for (int i = head[u]; i; i = e[i].nx) {
int to = e[i].v;
if (to == fa) continue;
dfs(u, to, dp + 1);
siz[u] += siz[to];
d[u] += dep[to];
}
}
void dfs2(int fa, int u) {
for (int i = head[u]; i; i = e[i].nx) {
int to = e[i].v;
if (to == fa) continue;
f[to] = d[to] - siz[to] - 1 + (f[u] - d[to] + 1 + (n - siz[to]));
dfs2(u, to);
}
}
signed main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
scanf("%d%d", &x, &y);
add(x, y);
add(y, x);
}
dfs(0, 1, 1);
f[1] = d[1];
dfs2(0, 1);
for (int i = 1; i <= n; i++) {
if (f[i] > ans) ans = f[i], l = i;
}
printf("%d", l);
}
|
