题目链接
输入输出格式
输入格式：
输出格式：
对于每个询问操作，输出一行答案。
输入输出样例
输入样例1：
6 5
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5
输出样例1：
3
1
2
说明
题解
这是这题的难点，弄懂了以后可以对线段树有个蛮大的提升
我们先把问题简化一下，假设这不是一棵树，只是一条连（已经树剖过了），给定每个元素的颜色，问有几段颜色（就是这题中颜色数量的定义），我们怎么做呢？
首先我们可以知道，为了保障时间复杂度，这题肯定是用线段树求解的，最先想到的是叶子节点的颜色个数为1，因为此时不存在有颜色会重复，按线段树的做法，现在要回溯求更大区间的颜色个数了，我们怎样求解呢？
其实分情况讨论一下就可以知道了：见下
第一种情况：
左区间：1231（颜色个数为4） 右区间：222（个数为1）
合并后：1231222（颜色个数为4+1=5）
这是第一种情况：没有重复
我们再来看第二种：
左区间：1231（颜色个数为4）右区间：121（个数为3）
合并后：1231121（颜色个数为4+3-1）
这就是第二种情况了，左区间的最后一个颜色和右区间的第一个颜色重合，也就重复了，所以总数减一
综上所述：我们用线段树维护左右颜色，区间颜色总数，就可以解决链情况下的此问题了
值得注意的是：不要忘记大区间要继承小区间的左右端点颜色
树上查询颜色个数
我们的操作时基于树形的，所以树剖过后，我们树剖的查询函数要略作修改。
如上图：树剖就是把两点之间剖成了若干条链，我们还是要解决不同的链之间颜色重复问题。上图已经很明朗了：解决top[a] 与 fa[top[a]] 颜色重复问题即可：
我写了个函数 Qc 来查询单点的颜色，其他学过树剖的应该不会太陌生
区间修改
与普通的树剖题修改无大异，注意线段树中的颜色数量更新即区间端点继承即可
细节很多，要注意，不仅在树上查询要注意端点的问题，在线段树也要注意，我调了很久都是因为在线段树的查询中没有注意端点问题！！！！
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;
struct Node{
int l,r,lazy,lc,rc,num;
int mid(){
return (l + r) >> 1;
}
}tree[MAXN << 2];
int n,m,a[MAXN];
int fa[MAXN],siz[MAXN],son[MAXN],dep[MAXN];
int top[MAXN],dfn[MAXN],tim,w[MAXN];
vector<int> E[MAXN];
void AddEdge(int u,int v){
E[u].push_back(v);
E[v].push_back(u);
}
void PushUp(int rt){
int rrt = rt << 1|1;
int ans = tree[rt << 1].num + tree[rrt].num;
tree[rt].lc = tree[rt << 1].lc,tree[rt].rc = tree[rrt].rc;
if(tree[rt << 1].rc == tree[rrt].lc)
ans--;
tree[rt].num = ans;
}
void PushDown(int rt){
int rrt = rt << 1|1;
tree[rt << 1].lazy = tree[rrt].lazy = tree[rt].lazy;
tree[rt << 1].num = tree[rrt].num = 1;
tree[rt << 1].lc = tree[rrt].rc = tree[rt].lazy;
tree[rrt].lc = tree[rt << 1].rc = tree[rt].lazy;
tree[rt].lazy = -1;
}
void Build(int l,int r,int rt){
tree[rt].l = l,tree[rt].r = r,tree[rt].lazy = -1;
if(l == r){
tree[rt].rc = tree[rt].lc = w[l];
tree[rt].num = 1;
return ;
}
int mid = tree[rt].mid();
Build(l,mid,rt << 1);
Build(mid+1,r,rt << 1|1);
PushUp(rt);
}
void Update(int l,int r,int rt,int val){
if(tree[rt].l == l && tree[rt].r == r){
tree[rt].num = 1;
tree[rt].lazy = val;
tree[rt].lc = tree[rt].rc = val;
return ;
}
if(tree[rt].lazy != -1)
PushDown(rt);
int mid = tree[rt].mid();
if(mid < l){
Update(l,r,rt << 1|1,val);
} else if(mid >= r) {
Update(l,r,rt << 1,val);
} else {
Update(l,mid,rt << 1,val);
Update(mid+1,r,rt << 1|1,val);
}
PushUp(rt);
}
int Query(int l,int r,int rt){
if(tree[rt].l == l && tree[rt].r == r){
return tree[rt].num;
}
int ret = 0,mid = tree[rt].mid();
if(tree[rt].lazy != -1)
PushDown(rt);
if(mid < l){
ret += Query(l,r,rt << 1|1);
} else if(mid >= r) {
ret += Query(l,r,rt << 1);
} else {
ret += Query(l,mid,rt << 1) + Query(mid+1,r,rt << 1|1);
if(tree[rt << 1].rc == tree[rt << 1|1].lc)
ret--;
}
return ret;
}
void dfs1(int u,int f){
dep[u] = dep[f] + 1;
fa[u] = f;
siz[u] = 1;
int sz = E[u].size(),maxsiz = -1;
for(int i = 0;i < sz;i++){
int v = E[u][i];
if(v == f)
continue;
dfs1(v,u);
siz[u] += siz[v];
if(siz[v] > maxsiz){
maxsiz = siz[v];
son[u] = v;
}
}
}
void dfs2(int u,int t){
top[u] = t;
dfn[u] = ++tim;
w[tim] = a[u];
if(!son[u])
return ;
dfs2(son[u],t);
int sz = E[u].size();
for(int i = 0;i < sz;i++){
int v = E[u][i];
if(v == fa[u] || v == son[u])
continue;
dfs2(v,v);
}
}
int Qcolor(int pos,int rt){
if(tree[rt].l == pos && tree[rt].r == pos)
return tree[rt].lc;
int mid = tree[rt].mid();
if(tree[rt].lazy != -1)
PushDown(rt);
if(pos <= mid)
return Qcolor(pos,rt << 1);
else
return Qcolor(pos,rt << 1|1);
}
int Qchain(int x,int y){
int ret = 0,Scolo,Fcolo;
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]])
swap(x,y);
ret += Query(dfn[top[x]],dfn[x],1);
Scolo = Qcolor(dfn[top[x]],1);
Fcolo = Qcolor(dfn[fa[top[x]]],1);
if(Scolo == Fcolo)
ret--;
x = fa[top[x]];
}
if(dep[x] > dep[y])
swap(x,y);
ret += Query(dfn[x],dfn[y],1);
return ret;
}
void mchain(int x,int y,int z){
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]])
swap(x,y);
Update(dfn[top[x]],dfn[x],1,z);
x = fa[top[x]];
}
if(dep[x] > dep[y])
swap(x,y);
Update(dfn[x],dfn[y],1,z);
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i = 1;i <= n;i++)
cin >> a[i];
for(int i = 1;i < n;i++){
int u,v;
cin >> u >> v;
AddEdge(u,v);
}
dfs1(1,0);
dfs2(1,1);
Build(1,n,1);
while(m--){
char op;
int x,y,z;
cin >> op;
if(op == 'Q'){
cin >> x >> y;
printf("%d\n",Qchain(x,y));
} else {
cin >> x >> y >> z;
mchain(x,y,z);
}
}
return 0;
}
附上几组写的时候用到的数据(洛谷论坛看到的)，还有参照的一位大佬的Blog
连接写的超级赞，本篇题解搬照与次，做日后方便查看使用:点我点我
输入
10 4
26 22 46 21 10 46 43 9 11 33
2 1
3 2
4 3
5 2
6 5
7 3
8 7
9 5
10 5
C 10 1 28
C 4 5 17
Q 7 10
Q 10 7
输出
3
3
输入
6 12
0 0 11 4 2 6
5 4
3 5
3 1
1 2
6 5
Q 2 6
C 3 1 3
Q 4 5
Q 2 6
Q 2 3
C 3 3 5
Q 2 1
C 3 4 3
C 2 4 2
Q 1 3
Q 1 6
C 4 3 6
输出
4
2
4
2
1
2