水题笔记_ [Sdoi2014]旅行 [树链剖分, 线段树]

天若有情天亦老 我为$Claris + 1s$

然而我并不能去R2 233333333333333

懵逼的 题目

扯淡的 题解

sb题…我去年怎么想到splay上面去了(可能是考虑删除和插入? 但是这题又不卡空间…lxl: 哦?)…

动态开点, 开$10^5$棵线段树维护每一种宗教就行了…

沙茶的 代码

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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
/**************************************************************
Problem: 3531
User: Cansult
Language: C++
Result: Accepted
Time:8952 ms
Memory:52392 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100000 + 5)
#define INF (0x7fffffff)
#define pii pair<int, int>
const int troot = 1;
using namespace std;
struct edg
{
int from, to, next;
}tb[MAXN << 1];
int tg[MAXN];
struct tnode
{
int zh, reli, deep, top, fa, hs, size, begin, end;
}ta[MAXN];
pii a[MAXN];
int n, cnta;
struct node
{
int le, ri, zh, sum, ls, rs;
}b[MAXN << 4];
int cntb, root[MAXN];
void adn(int from, int to)
{
static int cntt = -1;
tb[++cntt].next = tg[from];
tb[cntt].from = from;
tb[cntt].to = to;
tg[from] = cntt;
}
void push_up(int dq)
{
b[dq].zh = max(b[b[dq].ls].zh, b[b[dq].rs].zh);
b[dq].sum = b[b[dq].ls].sum + b[b[dq].rs].sum;
}
void xg(int& dq, int le, int ri, int wz, int zh)
{
if(!dq)
dq = ++cntb;
b[dq].le = le, b[dq].ri = ri;
if (le == ri)
{
b[dq].sum = b[dq].zh = zh;
return ;
}
int mi = (le + ri) >> 1;
if (wz > mi)
xg(b[dq].rs, mi + 1, ri, wz, zh);
else
xg(b[dq].ls, le, mi, wz, zh);
push_up(dq);
}
int cxmax(int dq, int le, int ri)
{
if (!dq)
return 0;
if (b[dq].le == le && b[dq].ri == ri)
return b[dq].zh;
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
return cxmax(b[dq].rs, le, ri);
else if (ri <= mi)
return cxmax(b[dq].ls, le, ri);
else
return max(cxmax(b[dq].ls, le, mi), cxmax(b[dq].rs, mi + 1, ri));
}
int cxsum(int dq, int le, int ri)
{
if (!dq)
return 0;
if (b[dq].le == le && b[dq].ri == ri)
return b[dq].sum;
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
return cxsum(b[dq].rs, le, ri);
else if (ri <= mi)
return cxsum(b[dq].ls, le, ri);
else
return cxsum(b[dq].ls, le, mi) + cxsum(b[dq].rs, mi + 1, ri);
}
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)
{
a[ta[dq].begin = ++cnta] = make_pair(ta[dq].reli, ta[dq].zh);
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].hs && tb[i].to != ta[dq].fa)
{
ta[tb[i].to].top = tb[i].to;
dfs(tb[i].to);
}
ta[dq].end = cnta;
}
void js()
{
for (int i = 1; i <= n; i++)
xg(root[a[i].first], 1, n, i, a[i].second);
}
int solvemax(int x, int y)
{
int re = -INF, dqroot = root[ta[x].reli];
while (ta[x].top != ta[y].top)
{
if (ta[ta[x].top].deep < ta[ta[y].top].deep)
swap(x, y);
re = max(re, cxmax(dqroot, ta[ta[x].top].begin, ta[x].begin));
x = ta[ta[x].top].fa;
}
if (ta[x].deep > ta[y].deep)
swap(x, y);
re = max(re, cxmax(dqroot, ta[x].begin, ta[y].begin));
return re;
}
int solvesum(int x, int y)
{
int re = 0, dqroot = root[ta[x].reli];
while (ta[x].top != ta[y].top)
{
if (ta[ta[x].top].deep < ta[ta[y].top].deep)
swap(x, y);
re += cxsum(dqroot, ta[ta[x].top].begin, ta[x].begin);
x = ta[ta[x].top].fa;
}
if (ta[x].deep > ta[y].deep)
swap(x, y);
re += cxsum(dqroot, ta[x].begin, ta[y].begin);
return re;
}
int main()
{
// cout << "Hello world!" << endl;
memset(tg, -1, sizeof(tg));
int q;
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++)
scanf("%d%d", &ta[i].zh, &ta[i].reli);
for (int i = 1; i < n; i++)
{
int srx, sry;
scanf("%d%d", &srx, &sry);
adn(srx, sry);
adn(sry, srx);
}
init(troot, 1);
dfs(troot);
js();
for (int i = 1; i <= q; i++)
{
char sre[4];
int srx, sry;
scanf("%s%d%d", sre, &srx, &sry);
if (sre[0] == 'Q')
{
if (sre[1] == 'S')
printf("%d\n", solvesum(srx, sry));
else
printf("%d\n", solvemax(srx, sry));
}
else
{
if (sre[1] == 'C')
xg(root[ta[srx].reli], 1, n, ta[srx].begin, 0), xg(root[ta[srx].reli = sry], 1, n, ta[srx].begin, ta[srx].zh);
else
xg(root[ta[srx].reli], 1, n, ta[srx].begin, ta[srx].zh = sry);
}
}
return 0;
}

/*
5 6
3 1
2 3
1 2
3 3
5 1
1 2
1 3
3 4
3 5
QS 1 5
CC 3 1
QS 1 5
CW 3 3
QS 1 5
QM 2 4
*/

By sb Cansult