本文主要是介绍树链剖分+线段树【SDOI2011】 bzoj2243 染色，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：
给一棵树，每个节点有一个颜色。写一个程序支持把两个点路径上的所有点染成一个颜色，查询两点之间的色段数量。
解题思路：
树链剖分+线段树
首先它是一颗树，而且是修改和查询两点路径上的颜色，可以想到树链剖分。
查询颜色段数可以用线段树维护区间颜色段数。
这道题涉及到区间合并，所以在线段树和lca的时候需要多记录一些东西，当前区间的最左边的颜色，最右边的颜色，已经求出的区间的左边的颜色。
我采用的做法是先求出lca，然后从左右两边各爬一边，就能有序的将所有的区间连在一起，当然大神告诉我可以左右同时爬，但是我不太会。
注意事项：
1、在树链剖分求lca的时候一定要写函数接口，不要把大段代码放在lca里，代码非常凌乱，不易差错；
2、打了标记要记得下传，时时刻刻思考要不要下传标记；
3、每次区间合并的时候要判断是否连接的部分是相同的颜色，如果相同要ans--；
4、从一侧爬的时候处理lca，另一侧就要避开lca，而且左右两条链合并的时候要判断颜色是否相同。
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 100100
using namespace std;
struct tree{int l,r,sum,ls,rs,lz;
}d[N*8];
int n,m,x,y,z,a,b;
char s[5];
int q[N];
int fir[N],nes[N*2],v[N*2];
bool pc[N*2];
int dep[N],fa[N],zon[N],sz[N],ld[N],xl[N],pos[N],top;
void dfs1(int c)
{dep[c]=dep[fa[c]]+1;sz[c]=1;for(int t=fir[c];t;t=nes[t]){if(pc[t]) continue;pc[t^1]=true;fa[v[t]]=c;dfs1(v[t]);sz[c]+=sz[v[t]];if(sz[v[t]]>sz[zon[c]]) zon[c]=v[t];}
}
void dfs2(int c)
{xl[++top]=c;pos[c]=top;ld[c]=c;if(zon[fa[c]]==c) ld[c]=ld[fa[c]];if(zon[c]) dfs2(zon[c]);for(int t=fir[c];t;t=nes[t]){if(pc[t] || v[t]==zon[c]) continue;dfs2(v[t]);}
}
void make_tree(int c,int l,int r)
{d[c].l=l;d[c].r=r;if(l==r){d[c].sum=1;d[c].ls=d[c].rs=q[xl[l]];d[c].lz=-1;return;}int mid=(l+r)/2;make_tree(c*2,l,mid);make_tree(c*2+1,mid+1,r);d[c].sum=d[c*2].sum+d[c*2+1].sum;if(d[c*2].rs==d[c*2+1].ls) d[c].sum--;d[c].ls=d[c*2].ls;d[c].rs=d[c*2+1].rs;d[c].lz=-1;
}
void push_down(int c)
{if(d[c].lz==-1) return;d[c].sum=1;d[c].ls=d[c].rs=d[c].lz;d[c*2].lz=d[c*2+1].lz=d[c].lz;d[c].lz=-1;return;
}
void change(int c)
{if(a<=d[c].l && b>=d[c].r) {d[c].lz=z;return;}push_down(c);int mid=(d[c].l+d[c].r)/2;if(a<=mid) change(c*2);if(b>mid) change(c*2+1);push_down(c*2);push_down(c*2+1);d[c].sum=d[c*2].sum+d[c*2+1].sum;if(d[c*2].rs==d[c*2+1].ls) d[c].sum--;d[c].ls=d[c*2].ls;d[c].rs=d[c*2+1].rs;d[c].lz=-1;
}
void lca_change(int x,int y)
{while(ld[x]!=ld[y]){if(dep[ld[x]]<dep[ld[y]]) swap(x,y);a=pos[ld[x]]; b=pos[x];change(1);x=fa[ld[x]];}if(dep[x]<dep[y]) swap(x,y);a=pos[y]; b=pos[x];change(1);
}
int query(int c,int &zs,int &ys)
{push_down(c);if(a<=d[c].l && b>=d[c].r){zs=d[c].ls; ys=d[c].rs;return d[c].sum;}int mid=(d[c].l+d[c].r)/2;if(b<=mid) return query(c*2,zs,ys);if(a>mid) return query(c*2+1,zs,ys);int zz,yy,ans=0;ans+=query(c*2,zs,yy);ans+=query(c*2+1,zz,ys);if(d[c*2].rs==d[c*2+1].ls) ans--;return ans;
}
int lca_query(int x,int y)
{int lx=x,ly=y;while(ld[lx]!=ld[ly]){if(dep[ld[lx]]<dep[ld[ly]]) swap(lx,ly);lx=fa[ld[lx]];}if(dep[lx]<dep[ly]) swap (lx,ly);int lca=ly,ans=0;int ls=-1,zs=-1,ys=-1,k1,k2;while(ld[x]!=ld[lca]){a=pos[ld[x]];b=pos[x];ans+=query(1,zs,ys);if(ls==ys) ans--;ls=zs;x=fa[ld[x]];}a=pos[lca];b=pos[x];ans+=query(1,zs,ys);if(ls==ys) ans--;k1=zs;ls=zs=ys=-1;while(ld[y]!=ld[lca]){a=pos[ld[y]];b=pos[y];ans+=query(1,zs,ys);if(ls==ys) ans--;ls=zs;y=fa[ld[y]];}if(y!=lca){a=pos[lca]+1; b=pos[y];ans+=query(1,zs,ys);if(ls==ys) ans--;}k2=zs;if(k1==k2) ans--;return ans;
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&q[i]);for(int i=2;i<2*n;i+=2){scanf("%d%d",&x,&y);nes[i]=fir[x];fir[x]=i; v[i]=y;nes[i^1]=fir[y];fir[y]=i^1; v[i^1]=x;}dfs1(1);dfs2(1);make_tree(1,1,n);for(int i=1;i<=m;i++){scanf("%s",s);if(s[0]=='Q'){scanf("%d%d",&x,&y);printf("%d\n",lca_query(x,y));}else{scanf("%d%d%d",&x,&y,&z);lca_change(x,y);}}return 0;
}这篇关于树链剖分+线段树【SDOI2011】 bzoj2243 染色的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
