水题笔记_ [JLOI2014]松鼠的新家 [树链剖分]

妈的智障

懵逼的 题目

传送至 Bilibili

扯淡的 题解

水, 线段树区间修改单点查询

沙茶的 代码

我在一下午的时间里

  • 查询和修改没有写push_down
  • 最后输出答案的时候把i搞成了a[i]
  • +=写成=
  • (b[dq].le + b[dq].ri) >> 1写成(le + ri) >> 1
  • 树链剖分把if (ta[ta[x].top].deep < ta[ta[y].top].deep), 写成if (ta[x].deep > ta[y].deep)

我怎么越来越沙茶了…

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (300000 + 5)
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define int long long
using namespace std;
struct node
{
int le, ri, zh, lazy;
}b[MAXN << 2];
struct tnode
{
int deep, fa, hs, top, start, end, size;
}ta[MAXN];
struct tedg
{
int from, to, next;
}tb[MAXN << 1];
int tg[MAXN], cntb, cnta, cnt[MAXN], a[MAXN];
node push_up(node ls, node rs)
{
node re;
re.lazy = 0;
re.le = ls.le, re.ri = rs.ri;
re.zh = ls.zh + rs.zh;
return re;
}
void push_down(int dq)
{
int &x = b[dq].lazy;
b[LS(dq)].zh += (b[LS(dq)].ri - b[LS(dq)].le + 1) * x;
b[RS(dq)].zh += (b[RS(dq)].ri - b[RS(dq)].le + 1) * x;
b[LS(dq)].lazy += x, b[RS(dq)].lazy += x;
x = 0;
}
void js(int dq, int le, int ri)
{
b[dq].le = le, b[dq].ri = ri;
b[dq].zh = b[dq].lazy = 0;
if (le == ri)
return ;
int mi = (le + ri) >> 1;
js(LS(dq), le, mi);
js(RS(dq), mi + 1, ri);
}
void xg(int dq, int le, int ri, int zh)
{
if (b[dq].le == le && b[dq].ri == ri)
{
b[dq].lazy += zh;
b[dq].zh += (ri - le + 1) * zh;
return ;
}
int mi = (b[dq].le + b[dq].ri) >> 1;
if (b[dq].lazy)
push_down(dq);
if (le > mi)
xg(RS(dq), le, ri, zh);
else if (ri <= mi)
xg(LS(dq), le, ri, zh);
else
xg(LS(dq), le, mi, zh), xg(RS(dq), mi + 1, ri, zh);
b[dq] = push_up(b[LS(dq)], b[RS(dq)]);
}
int cx(int dq, int wz)
{
if (b[dq].le == b[dq].ri)
return b[dq].zh;
if (b[dq].lazy)
push_down(dq);
int mi = (b[dq].le + b[dq].ri) >> 1;
if (wz <= mi)
return cx(LS(dq), wz);
else
return cx(RS(dq), wz);
}
void init(int dq, int deep)
{
ta[dq].deep = deep;
ta[dq].size = 1;
for (int i = tg[dq]; i; i = tb[i].next)
if (tb[i].to != ta[dq].fa)
{
ta[tb[i].to].fa = dq;
init(tb[i].to, deep + 1);
ta[dq].size += ta[tb[i].to].size;
if (ta[tb[i].to].size > ta[ta[dq].hs].size)
ta[dq].hs = tb[i].to;
}
}
void dfs(int dq)
{
ta[dq].start = ++cnta;
if (ta[dq].hs)
ta[ta[dq].hs].top = ta[dq].top, dfs(ta[dq].hs);
for (int i = tg[dq]; i; i = tb[i].next)
if (tb[i].to != ta[dq].fa && tb[i].to != ta[dq].hs)
{
ta[tb[i].to].top = tb[i].to;
dfs(tb[i].to);
}
ta[dq].end = cnta;
}
void solve(int x, int y, int zh)
{
while (ta[x].top != ta[y].top)
{
if (ta[ta[x].top].deep < ta[ta[y].top].deep)
swap(x, y);
xg(1, ta[ta[x].top].start, ta[x].start, 1);
x = ta[ta[x].top].fa;
}
if (ta[x].deep > ta[y].deep)
swap(x, y);
xg(1, ta[x].start, ta[y].start, 1);
}
void adn(int from, int to)
{
tb[++cntb].next = tg[from];
tb[cntb].from = from;
tb[cntb].to = to;
tg[from] = cntb;
}
main()
{
int n;
scanf("%lld", &n);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for (int i = 1; i < n; i++)
{
int srx, sry;
scanf("%lld%lld", &srx, &sry);
adn(srx, sry);
adn(sry, srx);
}
ta[1].fa = ta[1].top = 1;
init(1, 1);
dfs(1);
js(1, 1, n);
for (int i = 2; i <= n; i++)
solve(a[i], a[i - 1], 1), ++cnt[a[i]];
for (int i = 1; i <= n; i++)
printf("%lld\n", cx(1, ta[i].start) - cnt[i]);
}

/*
5
1 4 5 3 2
1 2
2 4
2 3
4 5
*/

By 日渐沙茶的 Cansult