「Codeforces 192E」Fools and Roads【树链剖分】

Time Limit: 4 Sec Memory Limit: 512 MB

Description

题目大意:有一颗 nn 个节点的树,kk 次旅行,问每一条边被走过的次数。

Input

第一行一个整数 nn (2n1052 \leqslant n \leqslant 10^5)。

接下来 n1n - 1 行,每行两个正整数 x,yx, y (1x,yn1 \leqslant x, y \leqslant n, xyx \neq y),表示 xxyy 之间有一条连边。

接下来一个整数 kk (0k1050 \leqslant k \leqslant 10^5)。

接下来 kk 行,每行两个正整数 x,yx, y (1x,yn1 \leqslant x, y \leqslant n),表示有一个从 xxyy 的旅行。

Output

n1n - 1 行,按输入顺序输出每一条边被走过的次数。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Sample Input #1:
5
1 2
1 3
2 4
2 5
2
1 4
3 5

Sample Input #2:
5
3 4
4 5
1 4
2 4
3
2 3
1 3
3 5

Sample Output

1
2
3
4
5
Sample Output #1:
2 1 1 1

Sample Output #2:
3 1 1 1

Solution

用树链剖分维护边权,对树上的边重新编号,编号 ii 表示点 ii 与其父亲节点的连边。注意修改操作中需要特判 u=vu = 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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int n, k, fa[maxn], dep[maxn], size[maxn];
int dfn, son[maxn], tid[maxn], top[maxn];
vector<int> G[maxn];
pair<int, int> e[maxn];
struct segment_tree {
int l, r, lazy;
} tree[maxn << 2];

void dfs1(int v, int f, int d) {
fa[v] = f, dep[v] = d;
size[v] = 1;
for (int u : G[v]) {
if (u == f) {
continue;
}
dfs1(u, v, d + 1);
size[v] += size[u];
if (size[u] > size[son[v]]) {
son[v] = u;
}
}
}

void dfs2(int v, int root) {
tid[v] = ++dfn, top[v] = root;
if (son[v]) {
dfs2(son[v], root);
}
for (int u : G[v]) {
if (u != fa[v] && u != son[v]) {
dfs2(u, u);
}
}
}

void pushdown(int k) {
if (tree[k].l < tree[k].r && tree[k].lazy) {
tree[k << 1].lazy += tree[k].lazy;
tree[k << 1 | 1].lazy += tree[k].lazy;
tree[k].lazy = 0;
}
}

void build(int k, int l, int r) {
tree[k].l = l, tree[k].r = r;
if (l == r) {
return;
}
int mid = (l + r) >> 1;
build(k << 1, l, mid);
build(k << 1 | 1, mid + 1, r);
}

void update(int k, int l, int r) {
pushdown(k);
if (tree[k].l == l && tree[k].r == r) {
tree[k].lazy++;
return;
}
int mid = (tree[k].l + tree[k].r) >> 1;
if (mid >= r) {
update(k << 1, l, r);
} else if (mid < l) {
update(k << 1 | 1, l, r);
} else {
update(k << 1, l, mid), update(k << 1 | 1, mid + 1, r);
}
}

int query(int k, int x) {
pushdown(k);
if (tree[k].l == tree[k].r) {
return tree[k].lazy;
}
int mid = (tree[k].l + tree[k].r) >> 1;
if (mid >= x) {
return query(k << 1, x);
} else {
return query(k << 1 | 1, x);
}
}

void change(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) {
swap(u, v);
}
update(1, tid[top[u]], tid[u]);
u = fa[top[u]];
}
if (u == v) {
return;
}
if (tid[u] > tid[v]) {
swap(u, v);
}
update(1, tid[son[u]], tid[v]);
}

int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
scanf("%d %d", &e[i].first, &e[i].second);
G[e[i].first].push_back(e[i].second), G[e[i].second].push_back(e[i].first);
}
dfs1(1, 0, 1);
dfs2(1, 1);
build(1, 1, n);
scanf("%d", &k);
while (k--) {
int u, v;
scanf("%d %d", &u, &v);
change(u, v);
}
for (int i = 1; i < n; i++) {
if (tid[e[i].first] > tid[e[i].second]) {
swap(e[i].first, e[i].second);
}
printf("%d%c", query(1, tid[e[i].second]), " \n"[i == n - 1]);
}
return 0;
}