我相信紫书上说的已经很清楚了，DFS一遍就好
首先随便找一个点为根节点，状态的定义是dp[i]表示i的子树的节点个数（包括他自己），所以实际上该点的最大子树数目就是max(dp[j],n-dp[i])，其中j是i的子树的节点号，n-dp[i]表示节点i的父亲树，在dfs求dp的时候顺便把答案找出来
由于比较简单，因此不计入100道动态规划
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int maxm=20010; struct Edge{ int v,nt; Edge(int a=0,int b=0):v(a),nt(b){}; }edge[maxm<<1]; int sz,n,x,y,times,fi[maxm],dp[maxm],ans,ansv,fa[maxm]; void init(); int dfs(int v); void addeage(); int main(){ ios_base::sync_with_stdio(false); cin>>times; while(times--){ init(); cin>>n; for(int i=1;i<n;++i){ cin>>x>>y; addeage(); } dfs(1); cout<<ansv<<' '<<ans<<endl; } return 0; } void init(){ sz=1; memset(fi,0,sizeof fi); memset(dp,-1,sizeof dp); ansv=0; ans=0x3f3f3f3f; } void addeage(){ edge[sz]=Edge(x,fi[y]); fi[y]=sz++; edge[sz]=Edge(y,fi[x]); fi[x]=sz++; } int dfs(int v){ if(dp[v]!=-1) return dp[v]; int te=0; dp[v]=1; for(int i=fi[v];i;i=edge[i].nt) if(edge[i].v!=fa[v]) fa[edge[i].v]=v,dp[v]+=dfs(edge[i].v),te=max(te,dfs(edge[i].v)); te=max(te,n-dp[v]); if(ans>te) ans=te,ansv=v; return dp[v]; }