洛谷P3478 [POI2008] STA-Station（换根dp）

题目链接

https://www.luogu.com.cn/problem/P3478

思路

对于$n=1e6$，我们考虑换根dp。

定义$f[u]$表示以$u$为根的子树中，所有节点的深度之和。定义$dp[u]$表示整棵树以$u$为根时，所有节点的深度之和。定义$siz[u]$表示以$u$为根的子树中节点的个数。

对于$f$的状态转移方程为：$f[u]=f[j]+siz[j](j\in son(u))$。

如上图所示，对于$dp$数组，当根从$1$号节点转移到$2$号节点时：

我们令$1$号节点为$u$，$2$号节点为$j$。从$1$号节点的父节点转移到$1$号节点的贡献为$sum$。

则传递到$j$的贡献为：$(f[u]-f[j]-siz[j])+(n-siz[j])+sum$。

状态转移方程为：$dp[u]=f[u]+sum$（其中，$sum$为转移到节点$u$上的贡献）。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int>pii;
const int N = 1e6 + 5, M = 1e6 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n;
int siz[N], f[N], dp[N];
vector<int>mp[N];
void dfs(int u, int fu, int deep)
{siz[u] = 1;f[u] = 0;for (int j : mp[u]){if (j == fu)continue;dfs(j, u, deep + 1);siz[u] += siz[j];f[u] += (f[j] + siz[j]);}
}
void dfs1(int u, int fu, int sum)
{dp[u] = f[u] + sum;for (int j : mp[u]){if (j == fu)continue;dfs1(j, u, sum + f[u] - f[j] - siz[j] + n - siz[j]);}
}
void solve()
{cin >> n;for (int i = 1, u, v; i < n; i++){cin >> u >> v;mp[u].push_back(v);mp[v].push_back(u);}dfs(1, -1, 0);dfs1(1, -1, 0);int idx = 1, maxx = 0;for (int i = 1; i <= n; i++){if (dp[i] > maxx){maxx = dp[i];idx = i;}}cout << idx << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}