Appearance
简介
换根 DP 是基于 树形 DP 的更高效算法。通常设
例
给定一棵
分析
以
flowchart A(($$1$$)) B(($$2$$)) C(($$3$$)) D(($$4$$)) E(($$5$$)) F(($$6$$)) G(($$7$$)) H(($$8$$)) A --> B & C B --> D & E C --> F & G & H
以
flowchart A(($$1$$)) B(($$2$$)) C(($$3$$)) D(($$4$$)) E(($$5$$)) F(($$6$$)) G(($$7$$)) H(($$8$$)) C --> A & F & G & H A --> B --> D & E
观察发现,原先
进一步地,设
先假定
边界条件为
cpp
// g[u]: 与 u 相连的点的集合
vector<int> g[];
void dfs1(int u, int fa) {
size[u] = 1;
d[u] = d[fa] + 1;
for (int v : g[u]) {
if (v == fa) continue;
dfs1(v, u);
size[u] += size[v];
}
}
void dfs2(int u, int fa) {
for (int v : g[u]) {
if (v == fa) continue;
f[v] = f[u] - size[v] + (n - size[v]);
dfs2(v, u);
}
}
int main() {
dfs1(1, 0);
for (int i = 1; i <= n; i ++)
f[1] += d[i];
dfs2(1, 0);
for (int i = 1; i <= n; i ++)
maxn = max(maxn, f[i]);
cout << maxn;
}