tree(换根dp)

题目大意: 一棵树,任意选择一个点为根,根的深度\(dep_{root}\)为0,整棵树的价值W=所有点的深度和,问你选择哪一个点作为根?

换根dp模板题

一般都是跑两边大法师,第一遍大法师是从根出发,处理出到达别的点的一些信息

然后第二遍大法师也是从根出发,但是每访问到一个节点都会转移一些信息

\[ f[y] = f[x]-siz[y]+n-siz[y](y= son[x]) \]

表示从x这个根转移到y这个根的话,首先要把从y引申出来的siz[y]条路径的长度全部减一

其次要把从x引申出来的所有不包含y的所有路径长度全部加一

PS:我们的f数组定义为:这个点到别的所有点的路径的和,并不是针对单个点,理解了这一点,转移也就很好理解了

代码如下:

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 666, inf = 214748364;

int n;
int f[N], dis[N], siz[N];

inline void dfs(int x, int yhm_fa)
{
int i, y;
siz[x] = 1;
for (i = head[x]; i; i = nex[i])
{
y = ver[i];
if (y == yhm_fa) continue;
dfs(y, x);
siz[x] += siz[y];
dis[x] += dis[y] + siz[y];
}
return;
}

inline void fuck(int x, int yhm_fa)
{
int i, y;
for (i = head[x]; i; i = nex[i])
{
y = ver[i];
if (y == yhm_fa) continue;
f[y] = f[x] - siz[y] + n - siz[y];
fuck(y, x);
}
}

signed main()
{
int i, x, y, res(inf);

n = read();
for (i = 1; i < n; ++ i)
{
x = read(), y = read();
add_edge(x, y), add_edge(y, x);
}

dfs(1, 0);

f[1] = dis[1];

fuck(1, 0);

for (i = 1; i <= n; ++ i) res = min(res, f[i]);

put(res);
return 0;
}