CSES – Subordinates

題目連結

題意

給一棵樹，問每個節點的子樹裡面有多少個點。而所謂子樹的範例請見下圖。

綠色圈起來的是 1 的子樹，藍色是 3 的子樹，紅色是 2 的子樹

解題方法

我們可以用 dfs 的方式遞迴計算每個節點的子樹有多少個節點，有點用到 DP 的概念。

狀態

dp[u] 表示 u 節點的子樹點數量

轉移

for(int v : G[u]){
    dp[u] += dp[v];
}

因為每個子樹之間是互不相干的，所以我們可以很輕鬆利用加法轉移!

初始條件

我們令所有點 dp[u] = 1，意思是子樹裡只有自己，不過這題要求的是不含自己的子樹大小，最後在 -1 即可。

#include <bits/stdc++.h>
using namespace std;
const int mxn = 2e5+5;
vector <int> dp(mxn, 1);
vector <int> G[mxn];
void dfs(int u){
    for(int v : G[u]){
        dfs(v);
        dp[u] += dp[v];
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 2;i <= n;i++){
        int x; cin >> x;
        G[x].push_back(i);
    }
    dfs(1);
    for(int i = 1;i <= n;i++){
        cout << dp[i]-1 << " \n"[i == n]; // 這題點自己不算
    }
}