一次智障的自我拯救

算法：dfs+记录 很基本的模板题

易错点：

• 双向边 所以添加边要小心 同时要开大2e5+10才行 （坑1）
• memset坑：memset是按位初始化 所以要小心使用sizeof而不是直接n+1
• 遍历所有邻接边要小心 是从h[u]开始而不是u

以上是我的智障全过程。。。引以为鉴

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
//图存储
//邻接矩阵 g[i][j]
//邻接表 
const int N = 2e5+10;
//每个节点开一个单链表 存储所有邻接点 h表示表头 ne表示表指针 e指明连到的节点编号
int h[N],e[N],ne[N],idx=0;

void init(int n){
    idx = 0;
    memset(h,-1,sizeof(int)*(n+1));//节点编号1-n
}
void add(int a,int b){
    e[idx] = b,ne[idx] = h[a];
    h[a] = idx++;
}
//traverse
/*
bool st[N] = {false};
void 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);
    }
}
void bfs(int u){
    memset(st,false,sizeof(st));
    queue<int> q;
    st[u] = true;
    q.push(u);
    int t = u;
    while(!q.empty()){
        t = q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i]){
            int j = e[i];
            if(!st[j]){
                st[j] = true;
                q.push(j);
            }
        }

    }
}
*/
//树的重心 dfs 846
bool st[N];
int cbm[N];//记录各个节点为分割点时 连通块数中最大值
int n;
int dfs(int u){
    st[u] = true;
    // cout<<u<<endl;
    int nowcbm = 0,nowsum = 0;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j = e[i];
        if(!st[j]){//除非是父节点
            int res = dfs(j);
            nowcbm = max(nowcbm,res);//当前最大连通块数目
            nowsum += res;
        }
    }
    cbm[u] = max(nowcbm,n-1-nowsum);
    return nowsum + 1;//返回当前节点为根子树的节点总数
}

int main(){
    ios::sync_with_stdio(false);
    int a,b;
    cin>>n;
    init(n);
    for(int i=0;i<n-1;i++){
        cin>>a>>b;
        //双向边
        add(a,b);
        add(b,a);
    }
    memset(st,false,sizeof(int)*(n+1));
    dfs(1);//随机选取一个节点就可以
    int res = n;
    for(int i=1;i<=n;i++){
        res = min(res,cbm[i]);
        // cout<<cbm[i]<<"----"<<st[i]<<endl;
    }
    cout<<res<<endl;
    return 0;
}