alan23273850 的刷題筆記
  1. 首頁
  2. /
  3. 4. CODEFORCES 題庫
  4. /
  5. 767-C. Garland

767-C. Garland

Tags: tree

出處：https://codeforces.com/contest/767/problem/C
提交：https://codeforces.com/contest/767/submission/111229792

問題：給定 $n\in[3,10^6]$ 個有根樹的節點號碼 $[1,n]$、連接狀況 (父節點是誰，定義樹根的父節點為 0)，以及各自的溫度 $[-100,100]$，現在想請問有沒有辦法三等份這整棵樹的溫度總和，使得每一棵子樹的溫度總和都是全部的三分之一。若無法則輸出 -1，若可行則輸出兩刀的子節點號碼。

解法：這題的作法其實可以意外地簡單，輸入資料的時候可以先算出整棵樹的溫度總和，然後就會有三分之一的值，接著一樣就是跑 DFS 回傳每個子樹 (延伸到樹葉) 的溫度和，一旦偵測到三分之一的話就把子樹的根記錄下來，然後此時的總和改成回傳 0，接著繼續找下一個三分之一的子樹，只要找滿兩刀就確定可以把這整棵樹三等分。實作細節的話要記得因為每一刀砍下來的子樹都不可能包含根，所以 DFS 要分成兩套，根節點用一套 dfs、其餘的非根節點用另外一套 dfs2。

心得：這題剛開始我是參考官方解答，分別找三分之一和三分之二的頂點，如果這兩類的頂點在同一棵子樹就是答案，否則就要找兩個不屬於同一棵樹的三分之一頂點作為解答。但是這樣實作起來非常困難，因為我們無法隨意地判斷兩個頂點是否屬於同一棵子樹，而且此作法無法推廣成任意 k 等分，所以多多參考神人的解答總是沒有壞處的。

延伸：根據此題解法易知，只要找到 k-1 刀底下的子樹總和都各自為 sum / k，就能確保此大樹可以切為 k 等分。

實作： 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <bits/stdc++.h>
using namespace std;

int n, index1, index2, sum;
vector<int> adj[1000001]; short t[1000001];

int dfs2(int u) {
    int ans = t[u];
    for (auto v: adj[u]) ans += dfs2(v);
    if (!index1 && ans*3==sum) {
        index1 = u;
        return 0; // very smart technique!
    }
    else if (index1 && ans*3==sum) index2 = u;
    return ans;
}

void dfs(int u) {
    for (auto v: adj[u]) {
        dfs2(v);
        if (index1 && index2) break;
    }
}

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
    cin >> n;
    for (int i=1; i<=n; i++) {
        int a; cin >> a >> t[i]; sum += t[i];
        adj[a].push_back(i);
    }
    if (sum % 3 != 0) cout << -1;
    else {
        dfs(adj[0][0]);
        if (index1 && index2) cout << index1 << " " << index2;
        else cout << -1;
    }
    return 0;
}

結果： Example image