之前都看过有换根dp，一直不知道是啥意思，本来弱弱树形dp都不太熟悉，不过今天工数课的时候突然想看一下，写个板子题练练吧。
对于我的理解，换根的题目一般是根不确定，而求得答案与根是谁有关，而且通过暴力枚举每个点为根节点即可得到答案。 这时候如果我们发现当该点的信息能够通过父节点的信息递推出来，那么我们可以考虑尝试换根dp，毕竟换根dp的本质还是递推，只不过通过父节点的信息递推本节点。
不难发现如果我们知道以父节点为根所有深度和那么该节点相对于父亲来说，该节点子树的深度比以父节点为根时的深度要小1，而不在该节点子树中的节点深度要比以父节点是根时的深度大1，由此得出以下递推关系 f s o n = f u + n − s i z e s o n − s i z e s o n f_{son}=f_u+n-size_{son}-size_{son} fson=fu+n−sizeson−sizeson
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) //#pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<random> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=1000010; int h[N],e[2*N],ne[2*N],idx; int n; ll dep[N]; int sz[N]; ll f[N]; int res=1; void dfs1(int u,int fa) { sz[u]=1; for(int i=h[u];i!=-1;i=ne[i]) { int j=e[i]; if(j==fa) continue; dep[j]=dep[u]+1; dfs1(j,u); sz[u]+=sz[j]; } } void dfs2(int u,int fa) { for(int i=h[u];i!=-1;i=ne[i]) { int j=e[i]; if(j==fa) continue; f[j]=f[u]+sz[1]-sz[j]-sz[j]; if(f[j]>f[res]) res=j; dfs2(j,u); } } void add(int a,int b) { e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } int main() { IO; int T=1; //cin>>T; while(T--) { cin>>n; memset(h,-1,sizeof h); for(int i=1;i<n;i++) { int a,b; cin>>a>>b; add(a,b),add(b,a); } dfs1(1,-1); for(int i=1;i<=n;i++) f[1]+=dep[i]; dfs2(1,-1); cout<<res<<'\n'; } return 0; }