树的重心（邻接表）

输入样例：

9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6

期望输出：

4

代码实现：

#include<bits/stdc++.h>
using namespace std;const int N =1e5+10 , M=2*N;int n,m;
int h[N],e[M],ne[M],idx;
bool vis[N];
int ans=N ;void add(int a,int b)//插入一条a指向b的边
{e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}int dfs(int u)//u代表的是第几个点
{vis[u]=1;int sum = 1,res =0; //sum 为当前子树的大小，res为把这一点删除后的连通块的最大值for(int i=h[u];i!=-1;i=ne[i]){int k=e[i];if(!vis[k]){int s = dfs(k); //当前子树的大小res = max(res,s);//看看所有子树哪个更大sum +=s;//求自己为父节点树的大小}}res = max(res,n-sum); //看看删除这个点的其他部分与最大子树哪个大ans = min(ans,res);//找到最小的答案return sum;
}int main()
{cin>>n;memset(h,-1,sizeof(h));for(int i=0;i<n-1;i++){int a ,b;cin>>a>>b;add(a,b);add(b,a);//因为是无向图，所以要新建两条边}dfs(1);//从哪个点开始搜cout<<ans<<endl;
}