Problem’s Wensite
- JLOI_2014松鼠的新家
Solution
- 这道题有两种解法，一种为树上差分，另一种为树链剖分，下面我简单解释一下。
- 树上差分：一种经典的做法，假设我们要对从$x$到$y$路径上的所有点权$+1$，我们可以在$x,fa[y]$加$1$，在$lca(x, y)$和$fa[lca(x, y)]$减一，最后把整棵树遍历一遍，点权累加，即可得到正确答案。
- 树链剖分：比较基础的操作，从$x$到$y$的路径上的点权$+1$，但要注意判重。
Code
树上差分
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
const int Maxn = 3e5 + 10;
inline int sc() {
int xx = 0, ff = 1; char cch = gc;
while(!isdigit(cch)) {
if(cch == '-') ff = -1; cch = gc;
}
while(isdigit(cch)) {
xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
}
return xx * ff;
}
inline void out(int x) {
if(x < 0) pc('-'), x = -x;
if(x >= 10)
out(x / 10);
pc(x % 10 + '0');
}
struct node {
int next, to, dis;
}t[Maxn << 1];
int n, cnt;
int a[Maxn], head[Maxn], dep[Maxn], w[Maxn], siz[Maxn], fa[Maxn], son[Maxn], top[Maxn];
inline void ADD(int from, int to) {
t[++cnt].next = head[from];
t[cnt].to = to;
head[from] = cnt;
}
inline void dfs1(int now, int Fa, int Dep) {
dep[now] = Dep;
fa[now] = Fa;
siz[now] = 1;
for(re int i = head[now]; i; i = t[i].next) {
int to = t[i].to;
if(to == Fa) continue;
dfs1(to, now, Dep + 1);
siz[now] += siz[to];
if(siz[son[now]] < siz[to])
son[now] = to;
}
}
inline void dfs2(int now, int topf) {
top[now] = topf;
if(!son[now]) return;
dfs2(son[now], topf);
for(re int i = head[now]; i; i = t[i].next) {
int to = t[i].to;
if(to == fa[now] || to == son[now]) continue;
dfs2(to, to);
}
}
inline void dfs3(int now,int Fa) {
// std :: cerr << now << " " << father << std :: endl;
for(re int i = head[now]; i; i = t[i].next){
int to = t[i].to;
if(to == Fa) continue;
dfs3(to, now);
w[now] += w[to];
}
}
inline int LCA(int a,int b) {
while(top[a] != top[b]) {
if(dep[top[a]] < dep[top[b]]) std :: swap(a,b);
a = fa[top[a]];
}
if(dep[a] > dep[b]) std :: swap(a,b);
return a;
}
int main() {
n = sc();
for(re int i = 1; i <= n; ++i)
a[i] = sc();
for(re int i = 1; i < n; ++i) {
int x = sc(), y = sc();
ADD(x, y), ADD(y, x);
}
dfs1(1, 0, 1), dfs2(1, 1);
for(int i = 2; i <= n; ++i) {
int x = a[i - 1], y = a[i];
int lca = LCA(x, y);
w[x]++, w[fa[y]]++;
w[lca]--, w[fa[lca]]--;
}
dfs3(1, 1);
for(re int i = 1; i <= n; ++i)
out(w[i]), pc('\n');
return 0;
}
// Coded by dy.树链剖分
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
const int Maxn = 3e5 + 10;
inline int sc() {
int xx = 0, ff = 1; char cch = gc;
while(!isdigit(cch)) {
if(cch == '-') ff = -1; cch = gc;
}
while(isdigit(cch)) {
xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
}
return xx * ff;
}
inline void out(int x) {
if(x < 0) pc('-'), x = -x;
if(x >= 10)
out(x / 10);
pc(x % 10 + '0');
}
struct node {
int next, to;
}t[Maxn << 1];
struct LST {
int data, tag;
}lst[Maxn << 2];
int n, cnt;
int a[Maxn], head[Maxn];
int fa[Maxn], siz[Maxn], son[Maxn], dep[Maxn], id[Maxn], aa[Maxn], top[Maxn];
inline void ADD(int from, int to) {
t[++cnt].next = head[from];
t[cnt].to = to;
head[from] = cnt;
}
inline void dfs1(int now, int Fa, int Dep) {
dep[now] = Dep;
fa[now] = Fa;
siz[now] = 1;
for(re int i = head[now]; i; i = t[i].next) {
int to = t[i].to;
if(to == Fa) continue;
dfs1(to, now, Dep + 1);
siz[now] += siz[to];
if(siz[son[now]] < siz[to])
son[now] = to;
}
}
inline void dfs2(int now, int topf) {
id[now] = ++cnt;
aa[cnt] = now;
top[now] = topf;
if(!son[now]) return;
dfs2(son[now], topf);
for(re int i = head[now]; i; i = t[i].next) {
int to = t[i].to;
if(to == fa[now] || to == son[now]) continue;
dfs2(to, to);
}
}
inline void pushdown(int k, int l, int r) {
if(!lst[k].tag) return;
lst[k << 1].tag += lst[k].tag;
lst[k << 1 | 1].tag += lst[k].tag;
int len = r - l + 1;
lst[k << 1].data += lst[k].tag * (len - (len >> 1));
lst[k << 1 | 1].data += lst[k].tag * (len >> 1);
lst[k].tag = 0;
}
inline void modify(int k, int l, int r, int x, int y, int z) {
if(x <= l && r <= y) {
lst[k].tag += z;
lst[k].data += z * (r - l + 1);
return ;
}
pushdown(k, l, r);
int mid = l + r >> 1;
if(x <= mid) modify(k << 1, l, mid, x, y, z);
if(y > mid) modify(k << 1 | 1, mid + 1, r, x, y, z);
lst[k].data = lst[k << 1].data + lst[k << 1 | 1].data;
}
inline int query(int k, int l, int r, int x) {
if(l == r && l == x) {
return lst[k].data;
}
int res = 0, mid = l + r >> 1;
pushdown(k, l, r);
if(x <= mid) res = query(k << 1, l, mid, x);
else res = query(k << 1 | 1, mid + 1, r, x);
return res;
}
inline void update(int x,int y) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) std :: swap(x, y);
modify(1, 1, cnt, id[top[x]], id[x], 1);
x = fa[top[x]];
}
if(dep[x] > dep[y]) std :: swap(x, y);
modify(1, 1, cnt, id[x], id[y], 1);
}
int main() {
n = sc();
for(re int i = 1; i <= n; ++i)
a[i] = sc();
for(re int i = 1; i < n; ++i) {
int x = sc(), y = sc();
ADD(x, y), ADD(y, x);
}
cnt = 0;
dfs1(1, 0, 1), dfs2(1, 1);
for(re int i = 1; i < n; ++i) {
update(a[i], a[i + 1]);
modify(1, 1, cnt, id[a[i + 1]], id[a[i + 1]], -1);
}
for(re int i = 1; i <= n; ++i) {
out(query(1, 1, cnt, id[i])), pc('\n');
}
return 0;
}
// Coded by dy.
rp++