树的深搜模板

int dfs(int u){
    st[u]=true;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(!st[j])dfs(j);
    }

}

深搜从该节点一直搜到叶子节点 $h[leaves]=-1$ 。

对于某个节点，dfs 可以得到其所有子树的总结点数，同时与父亲节点所在连通块的节点数作比较，取max 即为去除当前节点的连通块节点最大数量。

对于所有节点，取这个值的 min 即可

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2*N;
int e[M],ne[M],h[N];
int n,idx;
bool st[M];
int ans=M;
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
//the number of the son tree of u
int dfs(int u){
    //cout<<"dfs "<<u<<endl;
    st[u]=true;
    int sum=1,res=0;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        //cout<<u<<"-"<<j<<endl;
        if(!st[j]){
            int s=dfs(j);
            res=max(res,s);
            sum+=s;
        }
    }
    res=max(res,n-sum);//ÔÚÏÂÃæ×î´ó×ÓÊ÷µÄresÓëÉÏÃæÁ¬Í¨¿é È¡max 
    ans=min(ans,res);
    return sum; 

}
int main(){
    memset(h,-1,sizeof h);
    cin>>n;
    for(int i=1;i<=n-1;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs(1);
    cout<<ans<<endl;
}