[SDOI2014]旅行 题解
![[SDOI2014]旅行 题解](https://ksmeow.moe/wp-content/uploads/2018/06/180607b.jpg)
题目地址：洛谷：【P3313】[SDOI2014]旅行 – 洛谷、BZOJ：Problem 3531. — [Sdoi2014]旅行
题目描述
S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。
为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。
在S国的历史上常会发生以下几种事件：
“CC x c“：城市x的居民全体改信了c教；
“CW x w“：城市x的评级调整为w;
“QS x y“：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级总和；
“QM x y“：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级最大值。
由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。 为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。
题意简述
一棵树上每个点有颜色和权值，四种操作：
- 修改点的颜色
- 修改点的权值
- 询问路径上与起终点同色的点的权值和
- 询问路径上与起终点同色的点的权值最大值
保证询问的起终点同色
输入输出格式
输入格式：
输入的第一行包含整数N，Q依次表示城市数和事件数。
接下来N行，第i+l行两个整数Wi，Ci依次表示记录开始之前，城市i的评级和信仰。 接下来N-1行每行两个整数x，y表示一条双向道路。
接下来Q行，每行一个操作，格式如上所述。
输出格式：
对每个QS和QM事件，输出一行，表示旅行者记下的数字。
输入输出样例
输入样例#1：
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
输出样例#1：
8 9 11 3
说明
N，Q < =10^5 ， C < =10^5
数据保证对所有QS和QM事件，起点和终点城市的信仰相同；在任意时刻，城市的评级总是不大于10^4的正整数，且宗教值不大于C。
题解
可以每个颜色开一棵线段树做树剖，但是空间开不下。于是我们想到了动态开点。
复杂度O(n \log^2 n)。动态开点遇到null点可以直接return减小常数。
代码
// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
register char c = fgc();
while(!isdigit(c)) {
if(c == '-') neg = -1;
c = fgc();
}
while(isdigit(c)) {
res = (res << 1) + (res << 3) + c - '0';
c = fgc();
}
return res * neg;
}
inline bool isop(char c) {
return c == 'C' || c == 'Q';
}
inline int readop() {
char c;
while(!isop(c = fgc())) {}
if(c == 'C') {
if(fgc() == 'C') return 1;
else return 2;
} else {
if(fgc() == 'S') return 3;
else return 4;
}
}
const int MAXN = 100005;
int n, q;
std::vector<int> gra[MAXN];
struct Node {
int lch, rch, sum, mx;
} tr[MAXN << 8];
int rt[MAXN], tot;
inline void modify(int &o, int l, int r, int x, int v) {
if(!o) o = ++tot;
if(l == r) {
tr[o].sum = tr[o].mx = v; return;
}
int mid = (l + r) >> 1;
if(x <= mid) modify(tr[o].lch, l, mid, x, v);
else modify(tr[o].rch, mid + 1, r, x, v);
tr[o].sum = tr[tr[o].lch].sum + tr[tr[o].rch].sum;
tr[o].mx = std::max(tr[tr[o].lch].mx, tr[tr[o].rch].mx);
}
inline int querymx(int o, int l, int r, int ll, int rr) {
if(!o) return 0;
if(l >= ll && r <= rr) return tr[o].mx;
int mid = (l + r) >> 1, res = 0;
if(ll <= mid) res = std::max(res, querymx(tr[o].lch, l, mid, ll, rr));
if(rr > mid) res = std::max(res, querymx(tr[o].rch, mid + 1, r, ll, rr));
return res;
}
inline int querysum(int o, int l, int r, int ll, int rr) {
if(!o) return 0;
if(l >= ll && r <= rr) return tr[o].sum;
int mid = (l + r) >> 1, res = 0;
if(ll <= mid) res += querysum(tr[o].lch, l, mid, ll, rr);
if(rr > mid) res += querysum(tr[o].rch, mid + 1, r, ll, rr);
return res;
}
int fa[MAXN], siz[MAXN], son[MAXN], top[MAXN], dep[MAXN], dfn[MAXN], clk;
inline void dfs1(int u) {
siz[u] = 1;
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
if(v == fa[u]) continue;
fa[v] = u;
dep[v] = dep[u] + 1;
dfs1(v);
siz[u] += siz[v];
if(siz[v] > siz[son[u]]) son[u] = v;
}
}
inline void dfs2(int u, int tp) {
top[u] = tp; dfn[u] = ++clk;
if(son[u]) dfs2(son[u], tp);
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
if(v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
inline int querymx(int x, int y, int c) {
int res = 0, tx = top[x], ty = top[y];
while(tx != ty) {
if(dep[tx] > dep[ty]) {
std::swap(x, y); std::swap(tx, ty);
}
res = std::max(res, querymx(rt[c], 1, n, dfn[ty], dfn[y]));
y = fa[ty]; ty = top[y];
}
if(dep[x] > dep[y]) std::swap(x, y);
res = std::max(res, querymx(rt[c], 1, n, dfn[x], dfn[y]));
return res;
}
inline int querysum(int x, int y, int c) {
int res = 0, tx = top[x], ty = top[y];
while(tx != ty) {
if(dep[tx] > dep[ty]) {
std::swap(x, y); std::swap(tx, ty);
}
res += querysum(rt[c], 1, n, dfn[ty], dfn[y]);
y = fa[ty]; ty = top[y];
}
if(dep[x] > dep[y]) std::swap(x, y);
res += querysum(rt[c], 1, n, dfn[x], dfn[y]);
return res;
}
int w[MAXN], c[MAXN], op, x, y;
int main() {
n = readint(); q = readint();
for(int i = 1; i <= n; i++) {
w[i] = readint(); c[i] = readint();
}
for(int i = 1; i < n; i++) {
x = readint(); y = readint();
gra[x].push_back(y); gra[y].push_back(x);
}
dfs1(1);
dfs2(1, 1);
for(int i = 1; i <= n; i++) {
modify(rt[c[i]], 1, n, dfn[i], w[i]);
}
while(q--) {
op = readop(); x = readint(); y = readint();
if(op == 1) {
modify(rt[c[x]], 1, n, dfn[x], 0);
c[x] = y;
modify(rt[c[x]], 1, n, dfn[x], w[x]);
} else if(op == 2) {
w[x] = y;
modify(rt[c[x]], 1, n, dfn[x], w[x]);
} else if(op == 3) {
printf("%d\n", querysum(x, y, c[x]));
} else {
printf("%d\n", querymx(x, y, c[x]));
}
}
return 0;
}
