Loading... ## 思路 换根DP指的是一类树形DP，每个节点的贡献都由其所有相邻子树构成，在统计子节点子树贡献的同时也要考虑父节点子树的贡献。也就是说，任何节点都要作为根节点去考虑。然而如果真的把所有节点都作为根节点跑一遍DP，时间复杂度为$O(n^2)$。 如果存在某种情况，当前点所在子树以外的子树（也就是当前点若成为根时，父节点构成的子树）的贡献，可以通过某种方式从当前点子树推出来的话，那么一遍DP就能解决了。这种情况下，一般来说跑第一遍DP即可统计在假定根$root$的前提下，任何节点的子树对当前点的贡献$contribute(v)$。第二遍的时候，再加上利用$contribute(v)$推得“父子树”对当前节点的贡献$contribute(father)$即可。 接下来看一道简单例题： ## 例题1. [牛客NC15033 小G有一个大树](https://ac.nowcoder.com/acm/problem/15033) ### 题意 给定一棵树，求一个点$p$，使得去掉点$p$之后形成的森林，最大的$size$最小。给出$p$和$size$。 ### 分析 对于每个点$x$很容易求它的$size(x)$，这个通过一次搜索就能实现。接下来再做一次枚举，对于每个点，考虑将它作为根，那么与上一次搜索唯一不同的是要考虑父亲作为子树的大小，显然是$n-size(x)$，这样更新答案就可以了。 ### 代码 ```cpp #include <bits/stdc++.h> using namespace std; #define mp(x, y) make_pair(x, y) #define FOR(x, y, z) for (int x = y; x <= z; x++) typedef long long ll; #define N 1003 vector<int> nxt[N]; int n; int maxson[N], siz[N]; bool vis[N]; void dfs(int p) { vis[p] = 1; siz[p] = 1; for (auto v : nxt[p]) if (!vis[v]) { dfs(v); siz[p] += siz[v]; if (siz[v] > maxson[p]) maxson[p] = siz[v]; } } int main() { cin >> n; FOR(i, 1, n) { int x, y; cin >> x >> y; nxt[x].push_back(y); nxt[y].push_back(x); } int root = 1; dfs(root); int ans = 0, nodes = 0x7fffffff; FOR(i, 1, n) if (max(maxson[i], n - siz[i]) < nodes) { nodes = max(maxson[i], n - siz[i]); ans = i; } cout << ans << " " << nodes << endl; return 0; } ``` 以上这道题目，只需要知道可以将非当前子树本身的部分，当做一棵单独的子树来处理——即“换根”，就能非常容易写出结果。换根DP的难点是如何计算这棵“父子树”的贡献，接下来我们看一道需要一点处理的题目： ## 例题2. [洛谷P3478 [POI2008]STA-Station](https://www.luogu.com.cn/problem/P3478) ### 题意 给定一棵树，求一个节点$v$使得$v$为根节点时$\Sigma_{all}height(x)$最大，求这个最大值。 ### 分析 一遍DFS显然就能求出来深度（有特定根节点$root$下的），那么对于任意点$v$作为根节点，其子树深度都有了，外结点（父子树）深度怎么说呢？ **我们仅仅考虑它的直接父亲**$fa$，把根从$fa$换到$v$会导致父子树（包括$fa$）所有节点$height(x)++$和当前子树（包括$v$）所有节点$height(x)--$，那么当前点为根的答案就应该是 $$ f[v]=f[fa]+(n-size(v))-size(v) $$ 因为**只有直接父亲和孩子之间的直接转移满足这个式子，所以每一条边上都需要进行这个换根操作**。因此跑第二遍DFS就可以了。从先处理一下上一次$root$的$f[root]$然后从此处开始，那么每到一个节点它的$f[fa]$都是得到记录了的。 ### 代码 ```cpp #include <bits/stdc++.h> using namespace std; #define mp(x, y) make_pair(x, y) #define FOR(x, y, z) for (int x = y; x <= z; x++) typedef long long ll; #define N 1000006 int n; vector<int> nxt[N]; ll dp[N], sz[N], f[N]; bool vis[N]; ll ans, xx; void dfs1(int pos, int hei) //求所有节点的深度 { sz[pos] = 1; vis[pos] = 1; dp[pos] = hei; for (auto v : nxt[pos]) if (!vis[v]) { dfs1(v, hei + 1); sz[pos] += sz[v]; } } void dfs2(int u, int fa) { vis[u] = 1; if (fa) f[u] = f[fa] + n - 2 * sz[u]; if (f[u] > xx) xx = f[u], ans = u; for (auto v : nxt[u]) if (!vis[v]) dfs2(v, u); } int main() { cin >> n; FOR(i, 1, n - 1) { int x, y; cin >> x >> y; nxt[x].push_back(y); nxt[y].push_back(x); } dfs1(1, 0); FOR(i, 2, n) f[1] += dp[i]; memset(vis, 0, sizeof(vis)); dfs2(1, 0); cout << ans; return 0; } ``` ### Remind 这道题是一个典型。换根时**要求父亲节点是根节点**，那么就需要**使用DFS按顺序处理**每个节点为根节点的值，才能让子节点方便转移成根。 ## 例题3. [[USACO10MAR]Great Cow Gathering G](https://www.luogu.com.cn/problem/P2986/) ### 题意 树上每个点都有一定的奶牛，树边有距离，求一个点使得所有奶牛移动到这个点的距离总和最小，求这个最小值。 ### 分析 **带权中位数**的树上版本。处理方式是类似于前缀和，因为单向移动的时候“权”——在这里是奶牛的数量——是可加的。可以理解为，dfs回溯的时候，总是把下层的奶牛移动到上层来，然后在当前点聚集再向上移动。 第一遍dfs不说了，考虑从$fa$到$v$换根。子树贡献不变，那么就是父贡献，这分为两部分： 1. 属于$v$贡献到$fa$的部分, 应该回退. 这是需要减掉的部分. 2. 属于$fa$但不是$v$贡献过去的部分, 应该同第一遍dfs一样计算贡献. 这两部分写出来结果就出来了, 具体看代码: ### 代码 ```cpp #include <bits/stdc++.h> using namespace std; #define mp(x, y) make_pair(x, y) #define FOR(x, y, z) for (int x = y; x <= z; x++) typedef long long ll; #define N 100005 int n; ll c[N]; vector<pair<int, int>> nxt[N]; bool vis[N]; ll dp[N]; void dfs1(int p) { vis[p] = true; dp[p] = 0; //子树对当前节点的贡献 for (auto v : nxt[p]) if (!vis[v.first]) { dfs1(v.first); c[p] += c[v.first]; //整棵子树的牛牛数量 dp[p] += v.second * c[v.first] + dp[v.first]; //第一部分: 子节点v现有的牛牛走到当前节点 //第二部分: v子树牛牛走到v的贡献 } } ll ans = LLONG_MAX; void dfs2(int p, int fa, int d) { if (fa) { dp[p] = dp[fa] - c[p] * d + (c[fa] - c[p]) * d; c[p] = c[fa]; } if (dp[p] < ans) ans = dp[p]; for (auto v : nxt[p]) if (v.first != fa) dfs2(v.first, p, v.second); } int main() { cin >> n; FOR(i, 1, n) cin >> c[i]; FOR(i, 1, n - 1) { int u, v, d; cin >> u >> v >> d; nxt[u].push_back(mp(v, d)); nxt[v].push_back(mp(u, d)); } int rt = 1; dfs1(rt); dfs2(rt, 0, 0); cout << ans; return 0; } ``` ### Reminder WA了一阵子，是因为**换根完成之后忘记处理父亲节点的总奶牛数需要全部移动到当前节点**了！提醒需要注意换根的时候除了维护的贡献，还有**其他标记量不要忘记维护！** ## 参考资料 1. [[学习笔记]换根dp](https://www.luogu.com.cn/blog/sflsrick/note-how-to-change-root) 2. [【题目讲解】一起来做题#7（换根dp专题）](https://www.bilibili.com/video/BV1644y1x7sG) © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用，请随意赞赏