时间限制: 2 s
空间限制: 256000 KB
题目描述 Description
给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。
输入描述 Input Description
第一行包含2个整数n和m，分别表示节点数和操作数；
第二行包含n个正整数表示n个节点的初始颜色
下面n-1行每行包含两个整数 和 ，表示x和y之间有一条无向边。
下面m行每行描述一个操作：
“C a b c”表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c；
“Q a b”表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。
输出描述 Output Description
对于每个询问操作，输出一行答案。
样例输入 Sample Input
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
样例输出 Sample Output
3
1
2
数据范围及提示 Data Size & Hint
对于100%的数据1≤n≤104，1≤m≤105，1≤m≤109；
树链剖分+线段树
初始颜色可以单点修改插进去
染色操作：区间修改
查询操作：
区间查询+单点查询
区间查询：在同一条重链上的一起查
单点查询：每次查询完一条重链，询问重链顶端节点颜色和重链顶端的父节点颜色，如果相同，答案-1
#include<cstdio> #include<iostream> #define N 100001 using namespace std; int n,m,co[N],head[N],e_tot,tr_tot,p; int son[N],dep[N],fa[N],bl[N],sz,id[N]; struct edge{int to,next;}e[N*2]; struct node{int l,r,l_co,r_co,sum,f;}tr[N*2]; inline void add(int u,int v) { e[++e_tot].to=v;e[e_tot].next=head[u];head[u]=e_tot; e[++e_tot].to=u;e[e_tot].next=head[v];head[v]=e_tot; } void init() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&co[i]); int u,v; for(int i=1;i<n;i++) { scanf("%d%d",&u,&v); add(u,v); } } inline void dfs1(int x,int f) { son[x]++; for(int i=head[x];i;i=e[i].next) { if(e[i].to==f) continue; dep[e[i].to]=dep[x]+1; fa[e[i].to]=x; dfs1(e[i].to,x); son[x]+=son[e[i].to]; } } inline void dfs2(int k,int chain) { int m=0;sz++; id[k]=sz; bl[k]=chain; for(int i=head[k];i;i=e[i].next) { if(e[i].to==fa[k]) continue; if(son[e[i].to]>son[m]) m=e[i].to; } if(!m) return; dfs2(m,chain); for(int i=head[k];i;i=e[i].next) { if(e[i].to==m||e[i].to==fa[k]) continue; dfs2(e[i].to,e[i].to); } } inline void up(int k) { int l=k+1,r=k+(tr[k+1].r-tr[k+1].l+1<<1); tr[k].sum=tr[l].sum+tr[r].sum-(tr[l].r_co==tr[r].l_co); tr[k].l_co=tr[l].l_co;tr[k].r_co=tr[r].r_co; } inline void build(int l,int r) { tr_tot++; tr[tr_tot].l=l;tr[tr_tot].r=r; int y=tr_tot; if(l==r) return; int mid=l+r>>1; build(l,mid);build(mid+1,r); up(y); } inline void down(int k) { if(tr[k].l==tr[k].r) return; int l=k+1,r=k+(tr[k+1].r-tr[k+1].l+1<<1); tr[l].f=tr[l].l_co=tr[l].r_co=tr[r].f=tr[r].l_co=tr[r].r_co=tr[k].f; tr[l].sum=tr[r].sum=1; tr[k].f=0; } inline void change(int opl,int opr,int k,int w) { if(tr[k].l==opl&&tr[k].r==opr) { tr[k].f=tr[k].l_co=tr[k].r_co=w; tr[k].sum=1; return; } if(tr[k].f) down(k); int mid=tr[k].l+tr[k].r>>1,l=k+1,r=k+(tr[k+1].r-tr[k+1].l+1<<1); if(opr<=mid) change(opl,opr,l,w); else if(opl>mid) change(opl,opr,r,w); else {change(opl,mid,l,w);change(mid+1,opr,r,w);} up(k); } inline void solve_change(int u,int v,int w) { while(bl[u]!=bl[v]) { if(dep[bl[u]]<dep[bl[v]]) swap(u,v); change(id[bl[u]],id[u],1,w); u=fa[bl[u]]; } if(id[u]>id[v]) swap(u,v); change(id[u],id[v],1,w); } inline int query(int opl,int opr,int k) { if(opl==tr[k].l&&opr==tr[k].r){return tr[k].sum;} if(tr[k].f) down(k); int mid=tr[k].l+tr[k].r>>1,l=k+1,r=k+(tr[k+1].r-tr[k+1].l+1<<1); if(opr<=mid) return query(opl,opr,l); else if(opl>mid) return query(opl,opr,r); else { int t=query(opl,mid,l)+query(mid+1,opr,r); if(tr[l].r_co==tr[r].l_co) t--; return t; } } inline int point_query(int x,int k) { if(tr[k].l==tr[k].r) return tr[k].f; if(tr[k].f) down(k); int mid=tr[k].l+tr[k].r>>1,l=k+1,r=k+(tr[k+1].r-tr[k+1].l+1<<1); if(x<=mid) point_query(x,l); else point_query(x,r); } inline void solve_query(int u,int v) { int ans=0; while(bl[u]!=bl[v]) { if(dep[bl[u]]<dep[bl[v]]) swap(u,v); ans+=query(id[bl[u]],id[u],1); if(point_query(id[fa[bl[u]]],1)==point_query(id[bl[u]],1)) ans--; u=fa[bl[u]]; } if(id[u]>id[v]) swap(u,v); ans+=query(id[u],id[v],1); printf("%d ",ans); } inline void point_change(int k,int x,int w) { if(tr[k].l==tr[k].r) { tr[k].l_co=tr[k].r_co=tr[k].f=w; tr[k].sum=1; return; } int mid=tr[k].l+tr[k].r>>1,l=k+1,r=k+(tr[k+1].r-tr[k+1].l+1<<1); if(x<=mid) point_change(l,x,w); else point_change(r,x,w); up(k); } void solve() { for(int i=1;i<=n;i++) point_change(1,id[i],co[i]); char ch;int a,b,c; for(int i=1;i<=m;i++) { cin>>ch; if(ch=='C') { scanf("%d%d%d",&a,&b,&c); solve_change(a,b,c); } else { scanf("%d%d",&a,&b); solve_query(a,b); } } } int main() { init(); dfs1(1,0); dfs2(1,1); build(1,n); solve(); }
WA了1天，错误有二：
1、dfs1中continue写成return，然后不是TLE就是MLE
2、插入节点初始颜色时，看的大佬的博客，在build函数里插入，第i个叶子节点插co[id[i]]，但id[i]=j表示的是i号节点第j个被遍历，不是第i个遍历的是j号节点
不要盲目模仿大佬，想清楚细节