感觉动态开点线段树空间复杂度好优秀呀
树剖裸题
把每个宗教都开一颗线段树就可以了
但是我一直TLE
然后调了一个小时
为什么呢
因为我 #define max(x, y) (x > y ? x : y)
看起来好像可以减少常数的样子
我也是这么想的(作死
事实上
ans = max(ans, query(x, y))
类似这种语句中
query(x, y)会计算两次
然后就GG了
这告诉我们还是好好用库里的函数吧
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = + ;
const int M = + ;
#define isdigit(x) (x >= '0' && x <= '9') inline void read(int &ans) {
ans = ;
static char buf = getchar();
register int res = ;
for (; !isdigit(buf); buf = getchar())
if (buf == '-') res = -;
for (; isdigit(buf); buf = getchar())
ans = ans * + buf - '';
ans *= res;
} int tot, n, q;
int sz[N], hs[N], pos[N], fa[N], top[N], w[N], c[N], dep[N];
vector < int > E[N]; void dfs1(int x, int d, int f) {
dep[x] = d; fa[x] = f;
hs[x] = -; sz[x] = ;
int tmp = ;
for (int i = ; i < E[x].size(); i++) {
int u = E[x][i];
if (u == f) continue;
dfs1(u, d + , x);
sz[x] += sz[u];
if (tmp < sz[u])
tmp = sz[u], hs[x] = u;
}
} void dfs2(int x, int t) {
top[x] = t; pos[x] = ++tot;
if (hs[x] == -) return;
dfs2(hs[x], t);
for (int i = ; i < E[x].size(); i++)
if (E[x][i] != fa[x] && E[x][i] != hs[x])
dfs2(E[x][i], E[x][i]);
} int cnt;
int sum[M], maxn[M], ls[M], rs[M], root[N]; inline void pushUp(int o) {
maxn[o] = max(maxn[ls[o]], maxn[rs[o]]);
sum[o] = sum[ls[o]] + sum[rs[o]];
} void modify(int &o, int l, int r, int p, int c) {
if (!o) o = ++cnt;
if (l == r) {
sum[o] = maxn[o] = c;
return ;
}
int mid = l + r >> ;
if (p <= mid) modify(ls[o], l, mid, p, c);
else modify(rs[o], mid + , r, p, c);
pushUp(o);
} int querySum(int o, int l, int r, int L, int R) {
if (!o) return ;
if (l >= L && r <= R) return sum[o];
int mid = l + r >> , ans = ;
if (L <= mid) ans += querySum(ls[o], l, mid, L, R);
if (R > mid) ans += querySum(rs[o], mid + , r, L, R);
return ans;
} inline int querySum(int c, int x, int y) {
int f1 = top[x], f2 = top[y];
int ans = ;
while (f1 != f2) {
if (dep[f1] < dep[f2])
swap(x, y), swap(f1, f2);
ans += querySum(root[c], , n, pos[f1], pos[x]);
x = fa[f1]; f1 = top[x];
}
if (dep[x] > dep[y]) swap(x, y);
ans += querySum(root[c], , n, pos[x], pos[y]);
return ans;
} int queryMax(int o, int l, int r, int L, int R) {
if (!o) return ;
if (l >= L && r <= R) return maxn[o];
int mid = l + r >> , ans = ;
if (L <= mid) ans = max(ans, queryMax(ls[o], l, mid, L, R));
if (R > mid) ans = max(ans, queryMax(rs[o], mid + , r, L, R));
return ans;
} inline int queryMax(int c, int x, int y) {
int f1 = top[x], f2 = top[y];
int ans = ;
while (f1 != f2) {
if (dep[f1] < dep[f2])
swap(x, y), swap(f1, f2);
ans = max(ans, queryMax(root[c], , n, pos[f1], pos[x]));
x = fa[f1]; f1 = top[x];
}
if (dep[x] > dep[y]) swap(x, y);
ans = max(ans, queryMax(root[c], , n, pos[x], pos[y]));
return ans;
} int main() {
read(n); read(q);
for (int i = ; i <= n; i++)
read(w[i]), read(c[i]);
for (int i = ; i < n; i++) {
int u, v;
read(u); read(v);
E[u].push_back(v);
E[v].push_back(u);
}
dfs1(, , ); dfs2(, );
for (int i = ; i <= n; i++)
modify(root[c[i]], , n, pos[i], w[i]);
for (int i = ; i <= q; i++) {
char ch[]; scanf("%s", ch);
int x, y; read(x); read(y);
if (ch[] == 'C') {
if (ch[] == 'C') {
modify(root[c[x]], , n, pos[x], );
c[x] = y;
modify(root[y], , n, pos[x], w[x]);
}
else {
modify(root[c[x]], , n, pos[x], y);
w[x] = y;
}
}
else {
if (ch[] == 'S')
printf("%d\n", querySum(c[x], x, y));
else printf("%d\n", queryMax(c[x], x, y));
}
}
return ;
}