Hexo

树上DFS

基础板子

树上$DFS$一次性维护信息
$g$ : 邻接矩阵存储边的信息
$dep$ : 结点的深度
$fa$ : 父节点
$siz$ : 子节点个数

const int N = 200000 + 5;
vector<int> g[N];
int n;
int fa[N], dep[N], siz[N];

void dfs(int u, int p){
    fa[u] = p;                 // 记录父亲
    dep[u] = dep[p] + 1;       // 深度：根 dep[1]=1（dep[0]=0 作为哨兵）
    siz[u] = 1;                // 子树大小先算自己

    for(int v : g[u]){
        if(v == p) continue;   // 无向边防止走回父亲
        dfs(v, u);             // 先把孩子子树算完（后序关键）
        siz[u] += siz[v];      // 再把孩子子树大小累加到 u
    }
}

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++){
        g[i].clear();
    }

    for(int i=1;i<n;i++){
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dep[0] = 0;            // 哨兵
    dfs(1, 0);             // 根为 1，父亲设 0
}