当前位置：首页 > news >正文

20251201 - 换根dp总结

news 2026/3/27 2:19:20

20251201 - 换根dp总结

换根 dp，就是先预处理出一些信息，然后再转移。

一般的可以先考虑子树内的答案，在扩展到字树外。

扩展到字树外可以先考虑根节点到他的子节点的转移，在扩展到其他的点。

例题

P1395 会议

这道题可以先求出以 1 号点为根的子树的大小，那么子树外的大小就是 n - siz[u]。

预处理出来后，枚举每一个点，统计求 min 就好了。

#include <bits/stdc++.h>using namespace std;
#define ll long long
const int N = 1e5 + 7;
const int P = 998244353;
const int inf = (1 << 30);
template<class T> void read(T &x){x = 0;int f = 1;char ch = getchar();while(!(ch >= '0' && ch <= '9')){if(ch == '-') f = -f;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}x *= f;
}
int n;
vector<int> edges[N];
int pre[N], siz[N], dist[N];
inline void solve(int u, int from) {siz[u] = 1;for (auto v : edges[u]) {if (v == from) continue;pre[v] = u;solve(v, u);siz[u] += siz[v];}
}
inline void dfs(int u, int from) {for (auto v : edges[u]) {if (v == from) continue;dist[v] = dist[u] + 1;dfs(v ,u);}
}
int main(){read(n);for (int i = 1; i < n; i++) {int x, y;read(x), read(y);edges[x].push_back(y);edges[y].push_back(x);}pre[1] = -1;solve(1, 1);int id = 0, ans = inf;for (int i = 1; i <= n; i++) {int now_ans = 0;for (auto v : edges[i]) {if (pre[v] == i) {now_ans = max(now_ans, siz[v]);}else {now_ans = max(now_ans, n - siz[i]);}}if (now_ans < ans) {ans = now_ans;id = i;}}dfs(id, id);printf("%d %d\n", id, accumulate(dist + 1, dist + n + 1, 0));return 0;
}

P3478 STA-Station

题目可以转换成选择一个点，从这个点出发，到达每一个点的路径和最大。

那么可以设 siz[i] 为以 i 为根的子树的节点数，f[i] 为从 i 到子树内的点的和。

那么 f[u] 可以由 f[v] + siz[v] 来转移（因为从 u -> v，多了 siz[v] 个点）。

再设 c[i] 为从 i 到子树外的点的和。

当 u = 1 时，c[1] = 0，如果从 1 转移到 2，就会产生 (f[1] + c[1]) + (n - siz[2]) - (siz[2] + f[2]) 的贡献（总数 + 子树外 + 子树内）。

推广一下，就得 c[v] = (c[u] + f[u]) + (n - siz[v]) - (f[v] + siz[v])。

最终的答案就是 \(\max _{1 \le i \le n} f[i] + c[i]\)。

#include <bits/stdc++.h>using namespace std;
#define ll long long
const int N = 1e6 + 7;
const int P = 998244353;
const int inf = (1 << 30);
template<class T> void read(T &x){x = 0;int f = 1;char ch = getchar();while(!(ch >= '0' && ch <= '9')){if(ch == '-') f = -f;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}x *= f;
}
int n;
vector<int> edges[N];
ll siz[N], f[N], c[N];
inline void solve(int u, int from) {siz[u] = 1;for (auto v : edges[u]) {if (v == from) continue;solve(v, u);siz[u] += siz[v];f[u] += f[v] + siz[v];}
}
inline void dfs(int u, int from) {for (auto v : edges[u]) {if (v == from) continue;c[v] = (c[u] + f[u]) + (n - siz[v]) - (f[v] + siz[v]);dfs(v ,u);}
}
int main(){read(n);for (int i = 1; i < n; i++) {int x, y;read(x), read(y);edges[x].push_back(y);edges[y].push_back(x);}solve(1, 1);dfs(1, 1);// for (int i = 1; i <= n; i++) // printf("%d\n", c[i] + f[i]);ll id = 0, ans = 0;for (int i = 1; i <= n; i++) {if (c[i] + f[i] > ans)ans = c[i] + f[i], id = i;}printf("%lld\n", id);return 0;
}