解題區/解題區 - UVa

UVa 1674 - Lightning Energy Report

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給一棵樹，接著有數次操作將路徑 (u, v) 上的所有節點權重加上 k。

請問最後每一個點帶有的權重為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1 
9 
0 1
1 2
2 3
2 4
2 7
7 8
7 6
6 5
5 
1 4 10 
3 5 3 
0 8 5 
1 6 10 
4 4 100

Sample Output

1
2
3
4
5
6
7
8
9
10
Case #1: 
5 
25 
28 
3 
110 
3 
13 
18 
5

Solution

參照 zerojudge b322. 樹形鎖頭 的解法。

解說圖

A[] : 子樹總和
B[] : 節點權重

增加路徑 u 到 v 的權重為 k 時，路徑相當於 u 到某點 x 再到 LCA(u, v) 接著 y 最後 v。

那我們增加節點 u, v 的權重 B[u] += k, B[v] += k，減少其 LCA 的權重 B[LCA(u, v)] -= 2k，然後你會觀察 A[] 的部分，權重增加 k 的只會有 u-v 之間的所有節點。

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
#define MAXV 65536
int visited[MAXV];
vector<int> tree[MAXV];
int parent[MAXV], weight[MAXV];
int findp(int x) {
    return parent[x] == x ? x : (parent[x] = findp(parent[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)
        return 0;
    if(weight[x] > weight[y])
        weight[x] += weight[y], parent[y] = x;
    else
        weight[y] += weight[x], parent[x] = y;
    return 1;
}
// LCA
vector< pair<int, int> > Q[MAXV];// query pair, input index - node
int LCA[131072]; // [query time] input query answer buffer.
void tarjan(int u, int p) {// rooted-tree.
    parent[u] = u;
    for(int i = 0; i < tree[u].size(); i++) {//son node.
        int v = tree[u][i];
        if(v == p)	continue;
        tarjan(v, u);
        parent[findp(v)] = u;
    }
    visited[u] = 1;
    for(int i = 0; i < Q[u].size(); i++) {
        if(visited[Q[u][i].second]) {
            LCA[Q[u][i].first] = findp(Q[u][i].second);
        }
    }
}
int dfs(int u, int p, int weight[]) {
    int sum = weight[u];
    for(int i = 0; i < tree[u].size(); i++) {//son node.
        int v = tree[u][i];
        if(v == p)	continue;
        sum += dfs(v, u, weight);
    }
    return weight[u] = sum;
}
int main() {
    //	freopen("in.txt", "r+t", stdin);
    //	freopen("out2.txt", "w+t", stdout);
    int n, m, x, y;
    int testcase, cases = 0;
    int X[MAXV], Y[MAXV], K[MAXV];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            tree[i].clear();
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            tree[x].push_back(y);
            tree[y].push_back(x);
        }
        
        int weight[MAXV] = {}, extra[MAXV] = {};
        for (int i = 0; i < n; i++)
            visited[i] = 0, Q[i].clear();
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &X[i], &Y[i], &K[i]);
            Q[X[i]].push_back(make_pair(i, Y[i]));
            Q[Y[i]].push_back(make_pair(i, X[i]));
        }
        tarjan(0, -1);
        for (int i = 0; i < m; i++) {
            extra[LCA[i]] += K[i];
            weight[X[i]] += K[i];
            weight[Y[i]] += K[i];
            weight[LCA[i]] -= 2 * K[i];
        }
        dfs(0, -1, weight);
        
        printf("Case #%d:\n", ++cases);
        for (int i = 0; i < n; i++)
            printf("%d\n", weight[i] + extra[i]);
    }
    return 0;
}