🔗 UVA-10672 Marbles on a tree

tags: 樹(Tree) DFS 貢獻法

範例程式碼已於 UVA、瘋狂程設(CPE) 上皆測試通過。

題意

給定一個有 nn 個節點的樹，每個節點上都有一些彈珠，且整棵樹上總共有 nn 枚彈珠。

在每次移動中，我們可以選擇相鄰的兩個節點，將一枚彈珠從其中一個節點移動到另一個節點。移動可以是從父節點到子節點，也可以是從子節點移動到父節點。

返回使每個節點上都恰好有 一枚 彈珠所需的 最少 移動次數。

思路：深度優先搜索(DFS) + 貢獻法

由於題目給定的是一棵樹，雖然題目中看似有父節點和子節點的區分，但實際上本題中由於交換彈珠的方向是沒有限制的，因此可以將樹視為無向樹，即樹上的節點是沒有方向性的，故可以 任意選擇根節點 。

方法一：統計每個子樹需要和擁有的彈珠數量

對於任何一個節點，其 需要 的彈珠數量 needneed 為該子樹上的節點數量，而其 擁有 的彈珠數量 havehave 為其節點上的彈珠數量之和。而若 need>haveneed > have，則需要從其父節點將缺少的彈珠移動到該節點上，反之則需要將多餘的彈珠移動到其父節點，故該節點對答案的 貢獻 為 ∣need−have∣|need - have|。

而一個樹所需要的彈珠數量 needneed 和 havehave 可以透過遞迴的方式計算，其中 needneed 為所有子樹中的 needneed 總和再加上 11，havehave 為為所有子樹中的 havehave 之和再加上該節點的彈珠數量。

故可以透過 深度優先搜索(DFS) 的方式計算每個節點的 needneed 和 havehave，並在DFS的過程中計算答案。

複雜度分析

  • 時間複雜度：O(n)O(n)，其中 nn 為樹上的節點數量。
  • 空間複雜度：O(n)O(n)，遞迴需要的堆疊空間。
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
def dfs(u, fa):
    global ans
    p = 1 # need
    q = marbles[u] # have
    for v in g[u]:
        if v == fa:
            continue
        p2, q2 = dfs(v, u)
        p += p2
        q += q2
    ans += abs(p - q)
    return p, q

while True:
    n = int(input())
    if n == 0:
        break
    g = [[] for _ in range(n + 1)]
    marbles = [0] * (n + 1)

    for _ in range(n):
        u, m, d, *nodes = map(int, input().split())
        marbles[u] = m
        for v in nodes: # 建立無向樹
            g[u].append(v)
            g[v].append(u)
    
    ans = 0
    dfs(1, 0) # 以任意點當作根節點皆可
    print(ans)
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
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e4 + 5;
#define endl '\n'

int ans;
vector<vector<int>> g(N);
vector<int> marbles(N);

pair<int, int> dfs(int u, int fa){
    int p = 1, q = marbles[u]; // (need, have)
    for (int v : g[u]){
        if (v == fa) continue;
        pair<int, int> res = dfs(v, u);
        p += res.first;
        q += res.second;
    }
    ans += abs(p - q);
    return {p, q};
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, m, d, u, v;
    while (cin >> n && n){
        ans = 0;
        for (int i = 1; i <= n; ++i) g[i].clear();
        for (int i = 1; i <= n; ++i){
            cin >> u >> m >> d;
            marbles[u] = m;
            for (int j = 0; j < d; ++j){
                cin >> v;
                g[u].push_back(v);
                g[v].push_back(u);
            }
        }
        dfs(1, 0);
        cout << ans << endl;
    }
    return 0;
}

方法二：方法一優化

在方法一中，dfs\rm{dfs} 函數透過返回一個 tuple 或 pair (need,have)(need, have) 來計算每個節點的 needneed 和 havehave，但我們其實 只關注兩者的差值 ，故可以進一步優化。

將 dfs\rm{dfs} 函數改為只返回一個整數，若為 正數 則表示多餘的硬幣數量， 負數 表示缺少的硬幣數量。若只考慮該節點，不考慮子樹，返回值為 marbles[u]−1\rm{marbles}[u]- 1，考慮子樹後，返回值為 marbles[u]−1+∑vi∈g[u]vi≠fadfs(vi,u)\rm{marbles}[u] - 1 + \displaystyle\sum_{\substack{v_i \isin g[u] \\ v_i \neq fa}} \rm{dfs}(v_i, u)，且對答案的貢獻為 ∑vi∈g[u]vi≠fa∣dfs(vi,u)∣\displaystyle\sum_{\substack{v_i \isin g[u] \\ v_i \neq fa}} |\rm{dfs}(v_i, u) |。

複雜度分析

  • 時間複雜度：O(n)O(n)，其中 nn 為樹上的節點數量。
  • 空間複雜度：O(n)O(n)，遞迴需要的堆疊空間。
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
def dfs(u, fa): # 正數表示多餘，負數表示缺少
    global ans
    res = marbles[u] - 1
    for v in g[u]:
        if v == fa:
            continue
        res_v = dfs(v, u)
        ans += abs(res_v)
        res += res_v
    return res

while True:
    n = int(input())
    if n == 0:
        break
    g = [[] for _ in range(n + 1)]
    marbles = [0] * (n + 1)

    for _ in range(n):
        u, m, d, *nodes = map(int, input().split())
        marbles[u] = m
        for v in nodes: # 建立無向樹
            g[u].append(v)
            g[v].append(u)
    
    ans = 0
    dfs(1, 0) # 以任意點當作根節點皆可
    print(ans)
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
39
40
41
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e4 + 5;
#define endl '\n'

int ans;
vector<vector<int>> g(N);
vector<int> marbles(N);

int dfs(int u, int fa){ // 正數表示多餘，負數表示缺少
    int res = marbles[u] - 1;
    for (int v : g[u]){
        if (v == fa) continue;
        int res_v = dfs(v, u);
        ans += abs(res_v);
        res += res_v;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, m, d, u, v;
    while (cin >> n && n){
        ans = 0;
        for (int i = 1; i <= n; ++i) g[i].clear();
        for (int i = 1; i <= n; ++i){
            cin >> u >> m >> d;
            marbles[u] = m;
            for (int j = 0; j < d; ++j){
                cin >> v;
                g[u].push_back(v);
                g[v].push_back(u);
            }
        }
        dfs(1, 0);
        cout << ans << endl;
    }
    return 0;
}

類題

寫在最後

Cover photo is remixed from @Tekeli_liw3, thanks for their work!

說明的部分基本上是複製貼上，如果有不通順或與題意不同的地方，再麻煩留言提醒。