---
tags: CSES題解
---

CSES Problem Set — Subordinates 題解
===

題目
---
給一個公司的結構，計算每個員工有幾個下屬

### 輸入
第一行有一個整數 $n$ : 代表員工的數量。員工的編號為 $1,2,\dots,n$ 且一號員工是公司的最高負責人
之後，有 $n-1$ 個整數: 代表$2,3,\dots,n$ 編號員工的上司

### 輸出
輸出 $n$ 個整數 : 對每個員工編號為 $1,2,\dots,n$ 的下屬數量

想法
---
透過``DFS``走訪整棵樹，遞迴子樹結束後再加上子樹的大小。
由於樹的特殊性質，子樹只能透過父節點走到子樹以外的部分，只要``DFS``時特判父節點就不需要``visit``陣列來維護有沒有走訪過。

範例程式碼
---

#include<bits/stdc++.h>
#define int long long
using namespace std;
int cnt=1;
vector<int> Head(200500,0);
vector<int> Next(400500); //邊數量記得開兩倍
vector<int> To(400500);   //因為正反都要建
vector<int> Size(200500);
void addEdge(int u,int v){
    Next[cnt]=Head[u];
    To[cnt]=v;
    Head[u]=cnt++;
} 
/*************鍊式前向星建圖****************/

void dfs(int u,int par){
    Size[u]=0;
    for(int e=Head[u];e;e=Next[e]){
        int v=To[e];
        if(v!=par){
            dfs(v,u);
            Size[u]+=Size[v]+1; //遞迴完子樹加上子樹大小
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=2;i<=n;i++){
        int t;
        cin>>t;
        addEdge(i,t);
        addEdge(t,i);
    }
    dfs(1,1);
    for(int i=1;i<=n;i++) cout<<Size[i]<<" \n"[i==n];
    return 0;
}