BZOJ3631 [JLOI2014]松鼠的新家

BZOJ3631

树链剖分or树上差分 这里是树上差分的做法

考虑链上的差分,对于数组f,要对一段区间[a, b]区间+x,即f[a] += x, f[b + 1] -= x;

同理考虑树上差分,类似可得,对a到b路径上的所有点权+x,即f[a] += x, f[b] += x, f[lca(a, b)] -= x,  f[fa[lca(a, b)] -= x; 其中lca(a, b)为a, b的最近公共祖先,fa[x]为x的父节点。

最后只需dfs上传标记即可。


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
127
128
129
</pre>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cmath>
#include <algorithm>

 

const int N = 600000 + 10;

 

int a[N], beg[N], to[N], nxt[N], dep[N], anc[N][25], val[N];
int et;

 

int read(void);
void add(int , int );
void dfs(int );
void calc(int );
int lca(int , int );

 

int main(void)
{
int n = read();
for (int i = 1; i <= n; ++i)
a[i] = read();
for (int i = 1; i < n; ++i)
{
int u = read(), v = read();
add(u, v);
add(v, u);
}
dep[1] = 1;
dfs(1);
for (int i = 1; i < n; ++i)
{
int tmp = lca(a[i], a[i + 1]);
++val[a[i]];
++val[a[i + 1]];
--val[tmp];
--val[anc[tmp][0]];
}
calc(1);
for (int i = 1; i <= n; ++i)
printf("%d\n", val[i] - (a[1] != i));
return 0;
}

 

void dfs(int x)
{
for (int i = 1; (1 << i) <= dep[x]; ++i)
anc[x][i] = anc[anc[x][i - 1]][i - 1];
for (int i = beg[x]; i; i = nxt[i])
{
int y = to[i];
if (y != anc[x][0])
{
anc[y][0] = x;
dep[y] = dep[x] + 1;
dfs(y);
}
}
}

 

void calc(int x)
{
for (int i = beg[x]; i; i = nxt[i])
{
int y = to[i];
if (y != anc[x][0])
{
calc(y);
val[x] += val[y];
}
}
}

 

inline int lca(int x, int y)
{
if (dep[x] < dep[y])
std::swap(x, y);
for (int i = 0; dep[x] != dep[y]; ++i)
if ((1 << i) & (dep[x] - dep[y]))
x = anc[x][i];
if (x == y)
return x;
for (int i = log(dep[x]) / log(2) + 1; anc[x][0] != anc[y][0]; --i)
if (anc[x][i] != anc[y][i])
{
x = anc[x][i];
y = anc[y][i];
}
return anc[x][0];
}

 

inline void add(int u, int v)
{
++et;
nxt[et] = beg[u];
to[et] = v;
beg[u] = et;
}

 

inline int read(void)
{
char x;
while (!isdigit(x = getchar()))
;
int num = x - '0';
while (isdigit(x = getchar()))
(num *= 10) += x - '0';
return num;
}
<pre>

发表评论

电子邮件地址不会被公开。 必填项已用*标注