题目传送门
这题还是挺水的，还是YF哥哥最强了。（听说最近YF哥哥在一次模拟赛中虐场了，不愧是一代神犇）
其实我觉得YF哥哥有一点说错了，这题好像并不属于DP的范围，只是一个递推罢了。（YF哥哥不喜勿喷）
首先我们可以随便选一个节点作为树根，预处理出所有节点到第i号节点的距离和以当前节点为根的子树的大小。
然后我们取节点i和j，假设以第i号节点为根，j是i的一个儿子，现在我们要考虑以j号节点为根，所有节点到树根距离和的改变大小。
若以第i号节点为根时所有节点到第i号节点的距离和为f[i]，现在我们要把第j号节点提到树根处，那么节点j所在的子树内所有的节点到j的距离就等于到节点i的距离减一，其他的所有节点到节点j的距离就等于到节点i的距离加一。（这个是显而易见的，只要自己画画图，脑补一下就行了）
那么根据上述结论，我们可以得到f[j]=f[i]+n-size[j]-size[j]，也就是f[j]=f[i]+n-2*size[j]
然后就是递推了，最后扫一遍所有节点求最大值就行了。
附上AC代码：
#include <cstdio> #include <cctype> #define N 1000010 using namespace std; struct side{ long long to,nt; }s[N<<1]; long long n,x,y,num,h[N],sum[N],size[N],mx,ans; inline char nc(){ static char ch[1000010],*p1=ch,*p2=ch; return p1==p2&&(p2=(p1=ch)+fread(ch,1,100010,stdin),p1==p2)?EOF:*p1++; } inline void read(long long &a){ static char c=nc();long long f=1; for (;!isdigit(c);c=nc()) if (c=='-') f=-1; for (a=0;isdigit(c);a=a*10+c-'0',c=nc()); a*=f;return; } inline void add(long long x,long long y){ s[++num]=(side){y,h[x]},h[x]=num; s[++num]=(side){x,h[y]},h[y]=num; } inline void build(long long x,long long fa){ size[x]=sum[x]=1; for (long long i=h[x]; i; i=s[i].nt) if (s[i].to!=fa) build(s[i].to,x),size[x]+=size[s[i].to],sum[x]+=sum[s[i].to]+size[s[i].to]; return; } inline void so(long long x,long long fa){ for (long long i=h[x]; i; i=s[i].nt) if (s[i].to!=fa) sum[s[i].to]=sum[x]+n-2*size[s[i].to],so(s[i].to,x); return; } int main(void){ read(n); for (long long i=1; i<n; ++i) read(x),read(y),add(x,y); build(1,0),so(1,0); for (long long i=1; i<=n; ++i) if (sum[i]>mx) mx=sum[i],ans=i; printf("%lld",ans); return 0; }