欢迎访问~原文出处——

---

---

题意概括

　　一棵树，共n个节点。

　　让你支持以下两种操作，共m次操作：

　　1.　区间染色：给定两个节点，让你给树中链接这两个节点的路径染色。

　　2.　区间询问：给定两个节点，让你求出连接这两个节点的路径的色段数。比如说"112221"就是3段，分别是"11" "222" "1"

　　一开始给出初始染色情况。

　　n<=100000,m<=100000

---

题解

　　首先树链剖分，很明显。

　　然后线段树维护区间颜色。

　　我们可以写一个结构体，方便色段操作。

　　结构体保存4个值：当前色段的颜色总数v，左端和右端颜色：L,R；以及一个标记add：对于线段树，可以用作lazy标记，而对于色段的求和，可以用作空色段的标记（-2）；

　　那么色段相加就可以也一个运算符重载。这样很方便。

struct Tree{	int add,v,L,R;	Tree (){}	Tree (int x,int a,int b,int c){		add=x,v=a,L=b,R=c;	}}t[N*4];Tree operator + (Tree a,Tree b){	if (a.add==-2)		return b;	if (b.add==-2)		return a;	return Tree(-1,a.v+b.v-(a.R==b.L),a.L,b.R);}

　　然后就是线段树的维护了。

　　维护很简单，add标记打一打就可以了。

　　查询也很简单。反正空颜色段为（-2，0，0，0）,合并结果就是把两个色段加起来。

　　对于在树上取多段链，首先对于两个纵向的链我们求出色段。

　　然后最终两个点会到同一条链上。（如果没看懂这个，那么您还得重新学学树剖）

　　然后随便选一个色段翻转一下（你喜欢那个就那个，比如我翻转了上面的那个），然后再求出这两个点之间的色段，全部加起来就可以了。

---

代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N=100005;struct Gragh{	int cnt,y[N*2],nxt[N*2],fst[N];	void clear(){		cnt=0;		memset(fst,0,sizeof fst);	}	void add(int a,int b){		y[++cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt;	}}g;struct Tree{	int add,v,L,R;	Tree (){}	Tree (int x,int a,int b,int c){		add=x,v=a,L=b,R=c;	}}t[N*4];Tree operator + (Tree a,Tree b){	if (a.add==-2)		return b;	if (b.add==-2)		return a;	return Tree(-1,a.v+b.v-(a.R==b.L),a.L,b.R);}int n,m,v[N],fa[N],size[N],depth[N],son[N],top[N],p[N],ap[N],cnp;void Get_Gen_Info(int rt,int pre,int d){	fa[rt]=pre,size[rt]=1,son[rt]=-1,depth[rt]=d;	for (int i=g.fst[rt];i;i=g.nxt[i])		if (g.y[i]!=pre){			int s=g.y[i];			Get_Gen_Info(s,rt,d+1);			size[rt]+=size[s];			if (son[rt]==-1||size[s]>size[son[rt]])				son[rt]=s;		}}void Get_Pos(int rt,int tp){	top[rt]=tp,p[rt]=++cnp,ap[cnp]=rt;	if (son[rt]==-1)		return;	else		Get_Pos(son[rt],tp);	for (int i=g.fst[rt];i;i=g.nxt[i]){		int s=g.y[i];		if (s!=son[rt]&&s!=fa[rt])			Get_Pos(s,s);	}}void pushup(int rt){	t[rt]=t[rt<<1]+t[rt<<1|1];}void build(int rt,int le,int ri){	t[rt].add=-1;	if (le==ri){		t[rt].L=t[rt].R=v[ap[le]];		t[rt].v=1;		return;	}	int mid=(le+ri)>>1,ls=rt<<1,rs=ls|1;	build(ls,le,mid);	build(rs,mid+1,ri);	pushup(rt);}void pushdown(int rt){	int ls=rt<<1,rs=ls|1;	int &a=t[rt].add;	if (a==-1)		return;	t[ls].L=t[rs].L=t[ls].R=t[rs].R=a;	t[ls].v=t[rs].v=1;	t[ls].add=t[rs].add=a;	a=-1;}void update(int rt,int le,int ri,int xle,int xri,int v){	if (ri
          
           xri) return; if (xle<=le&&ri<=xri){ t[rt].add=t[rt].L=t[rt].R=v; t[rt].v=1; return; } pushdown(rt); int mid=(le+ri)>>1,ls=rt<<1,rs=ls|1; update(ls,le,mid,xle,xri,v); update(rs,mid+1,ri,xle,xri,v); pushup(rt);}Tree query(int rt,int le,int ri,int xle,int xri){ if (ri
           
            xri) return Tree(-2,0,0,0); if (xle<=le&&ri<=xri) return t[rt]; pushdown(rt); int mid=(le+ri)>>1,ls=rt<<1,rs=ls|1; return query(ls,le,mid,xle,xri)+query(rs,mid+1,ri,xle,xri);}void Tupdate(int a,int b,int c){ int f1=top[a],f2=top[b]; while (f1!=f2){ if (depth[f1]
            
             depth[b]) swap(a,b); update(1,1,n,p[a],p[b],c);}int solve(int a,int b){ int f1=top[a],f2=top[b]; Tree r1(-2,0,0,0),r2(-2,0,0,0); while (f1!=f2){ if (depth[f1]
             
              depth[b]) swap(a,b),swap(r1,r2); swap(r1.L,r1.R); return (r1+query(1,1,n,p[a],p[b])+r2).v;}int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&v[i]); g.clear(); for (int i=1,a,b;i