(dfs+ tree DP) acwing 846 Center of gravity of tree

846. The center of gravity of the tree

Topic link https://www.acwing.com/problem/content/848/
subject ：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=1e5+10;
int n;
int res=N;
bool vis[N];
vector<int > q[N];
int dfs(int u){
    
    vis[u]=1;
    int rs=0;
    int sum=0;
    for(int i=0;i<q[u].size();i++){
    
        if(!vis[q[u][i]]){
    
            int t=dfs(q[u][i]);
            sum+=t;
            rs=max(rs,t);
        }

    }
    rs=max(rs,n-sum-1);
    res=min(rs,res);
    return sum+1;
}
int main(){
    
    cin>>n;
    int a,b;
    for(int i=1;i<n;i++){
    
        scanf("%d%d",&a,&b);
        q[a].push_back(b);
        q[b].push_back(a);
    }
    dfs(1);
    cout<<res;
    return 0;
}