Luogu P3313 [SDOI2014]旅行

qwp

树剖快忘干净了,找道题做做。

树剖,每种宗教用一棵线段树维护。空间复杂度无法承受,所以动态开点。

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
#include <bits/stdc++.h>

const int N = 1e5 + 233;
int n, q, num, qwq, root[N], w[N], c[N];
int dep[N], siz[N], son[N], tp[N], fa[N], id[N], g2r[N];
std::vector<int> e[N];
struct SegTree {
int ls, rs, sum, mx;
} t[N << 4];

void dfs1(int x, int f) {
dep[x] = dep[f] + 1, fa[x] = f, siz[x] = 1;
for (auto y : e[x]) {
if (y == f) continue;
dfs1(y, x);
siz[x] += siz[y];
if (siz[y] > siz[son[x]]) son[x] = y;
}
}

void dfs2(int x, int tpp) {
tp[x] = tpp, id[x] = ++qwq, g2r[qwq] = x;
if (!son[x]) return;
dfs2(son[x], tpp);
for (auto y : e[x])
if (y != fa[x] && y != son[x]) dfs2(y, y);
}

void modify(int &p, int l, int r, int x, int d) {
if (!p) p = ++num;
if (l == r) return (void)(t[p].sum = t[p].mx = d);
int mid = (l + r) >> 1;
x <= mid ? modify(t[p].ls, l, mid, x, d) : modify(t[p].rs, mid + 1, r, x, d);
t[p].sum = t[t[p].ls].sum + t[t[p].rs].sum;
t[p].mx = std::max(t[t[p].ls].mx, t[t[p].rs].mx);
}

int querySum(int p, int l, int r, int pl, int pr) {
if (l >= pl && r <= pr) return t[p].sum;
int mid = (l + r) >> 1, ret = 0;
if (pl <= mid) ret += querySum(t[p].ls, l, mid, pl, pr);
if (pr > mid) ret += querySum(t[p].rs, mid + 1, r, pl, pr);
return ret;
}

int queryMax(int p, int l, int r, int pl, int pr) {
if (l >= pl && r <= pr) return t[p].mx;
int mid = (l + r) >> 1, ret = -0x3f3f3f3f;
if (pl <= mid) ret = std::max(ret, queryMax(t[p].ls, l, mid, pl, pr));
if (pr > mid) ret = std::max(ret, queryMax(t[p].rs, mid + 1, r, pl, pr));
return ret;
}

int askSum(int x, int y, int k) {
int ret = 0;
while (tp[x] != tp[y]) {
if (dep[tp[x]] < dep[tp[y]]) std::swap(x, y);
ret += querySum(root[k], 1, n, id[tp[x]], id[x]);
x = fa[tp[x]];
}
if (dep[x] > dep[y]) std::swap(x, y);
return ret + querySum(root[k], 1, n, id[x], id[y]);
}

int askMax(int x, int y, int k) {
int ret = -0x3f3f3f3f;
while (tp[x] != tp[y]) {
if (dep[tp[x]] < dep[tp[y]]) std::swap(x, y);
ret = std::max(ret, queryMax(root[k], 1, n, id[tp[x]], id[x]));
x = fa[tp[x]];
}
if (dep[x] > dep[y]) std::swap(x, y);
return std::max(ret, queryMax(root[k], 1, n, id[x], id[y]));
}

signed main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; ++i) scanf("%d%d", w + i, c + i);
for (int i = 1, x, y; i < n; ++i) {
scanf("%d%d", &x, &y);
e[x].push_back(y), e[y].push_back(x);
}
dfs1(1, 0), dfs2(1, 1);
for (int i = 1; i <= n; ++i) modify(root[c[i]], 1, n, id[i], w[i]);
for (int i = 1; i <= q; ++i) {
char op[20];
int x, y;
scanf("%s%d%d", op, &x, &y);
if (op[0] == 'C') {
if (op[1] == 'C') {
modify(root[c[x]], 1, n, id[x], 0);
modify(root[y], 1, n, id[x], w[x]);
c[x] = y;
} else {
modify(root[c[x]], 1, n, id[x], y);
w[x] = y;
}
} else {
if (op[1] == 'S') {
printf("%d\n", askSum(x, y, c[x]));
} else {
printf("%d\n", askMax(x, y, c[x]));
}
}
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×