https://www.luogu.org/problemnew/show/P2486

轻重链剖分后，问题转化为一个链上的问题；

线段树维护区间内的颜色段数量，左端点、右端点的颜色；

线段树注意事项 {

　　合并时判断两个区间的相邻端点是否相同；

　　查询时同上，但要注意是否两段是不是都在查询区间内；

　　lazy_tag和更新颜色，嘻嘻嘻。

}

p.s 树上查询颜色段要判断两条链的端点是否颜色相同；

特别地，对于在同一条链上的两个节点之间的查询，要判断两个点和与它相邻点的颜色是否相同。

代码如下 :

1 // 15owzLy1  2 //luogu2486.cpp  3 //2018 09 26      18:38:11  4 #include 
      
         5 #include 
       
          6 #include 
        
           7 #include 
         
            8 #define lson tl, mid, rt<<1  9 #define rson mid+1, tr, rt<<1|1 10 typedef long long ll; 11 typedef double db; 12 using namespace std; 13  14 const int N = 100005; 15 struct node { int l, r, cnt; }; 16 struct info { 17     int next, to; 18 }edge[N<<1]; 19 int head[N], dfn[N], size[N], hson[N], fa[N], dep[N], q, n; 20 int front[N], cl[N]; 21  22 template
          
           inline void read(T &x_) { 23     x_=0;bool f_=0;char c_=getchar(); 24     while(c_<'0'||c_>'9'){f_|=(c_=='-');c_=getchar();} 25     while(c_>='0'&&c_<='9'){x_=(x_<<1)+(x_<<3)+(c_^48);c_=getchar();} 26     x_=f_?-x_:x_; 27 } 28  29 struct Segment_Tree { 30     node t[N<<2]; int lazy[N<<2]; 31     inline void push_up(int rt) { 32         t[rt].cnt=t[rt<<1].cnt+t[rt<<1|1].cnt; 33         if(t[rt<<1].r==t[rt<<1|1].l) t[rt].cnt--; 34         t[rt].l=t[rt<<1].l, t[rt].r=t[rt<<1|1].r; 35     } 36     inline void spread(int rt) { 37         t[rt<<1].cnt=1; t[rt<<1|1].cnt=1; 38         t[rt<<1].l=t[rt<<1|1].r=t[rt<<1].r=t[rt<<1|1].l= 39         lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt]; 40         lazy[rt]=0; 41     } 42     void update(int del, int l, int r, int tl, int tr, int rt) { 43         if(l<=tl&&tr<=r) { 44             t[rt].cnt=1; t[rt].l=t[rt].r=lazy[rt]=del; 45             return ; 46         } 47         if(lazy[rt]) spread(rt); 48         int mid=(tl+tr)>>1; 49         if(mid>=l) update(del, l, r, lson); 50         if(mid
           
            >1, res=0, k=0; 57 if(mid>=l) res+=query(l, r, lson), ++k; 58 if(mid
            
             =2) res--; 60 return res; 61 } 62 int ask_cl(int pos, int tl, int tr, int rt) { 63 if(tl==tr) return t[rt].l; 64 if(lazy[rt]) spread(rt); 65 int mid=(tl+tr)>>1; 66 if(mid>=pos) return ask_cl(pos, lson); 67 else return ask_cl(pos, rson); 68 } 69 }T; 70 71 inline void jb(int u, int v) { 72 edge[++edge[0].to].to=v; 73 edge[edge[0].to].next=head[u]; 74 head[u]=edge[0].to; 75 } 76 77 void dfs(int u) { 78 size[u]=1; 79 for(int i=head[u];i;i=edge[i].next) { 80 int v=edge[i].to; 81 if(v==fa[u]) continue; 82 fa[v]=u; dep[v]=dep[u]+1; 83 dfs(v); 84 size[u]+=size[v]; 85 if(size[hson[u]]
             
              dep[front[v]]) swap(u, v);102 T.update(del, dfn[front[v]], dfn[v], 1, n, 1);103 v=fa[front[v]];104 }105 if(dep[u]>dep[v]) swap(u, v);106 T.update(del, dfn[u], dfn[v], 1, n, 1);107 }108 109 inline int query(int u, int v) {110 int res=0, clu=-1, clv=-1, tmp, k=0;111 while(front[u]!=front[v]) {112 if(dep[front[u]]>dep[front[v]])113 swap(u, v), swap(clu, clv);114 res+=T.query(dfn[front[v]], dfn[v], 1, n, 1);115 tmp=T.ask_cl(dfn[v], 1, n, 1);116 if(clv==tmp) --res;117 clv=T.ask_cl(dfn[front[v]], 1, n, 1);118 v=fa[front[v]];119 }120 if(dep[u]>dep[v])121 swap(u, v), swap(clu, clv);122 if(clu==T.ask_cl(dfn[u], 1, n, 1)) res--, ++k;123 if(clv==T.ask_cl(dfn[v], 1, n, 1)) res--, ++k;124 res+=T.query(dfn[u], dfn[v], 1, n, 1);125 return res;126 }127 128 int main() {129 #ifndef ONLINE_JUDGE130 freopen("luogu2486.in","r",stdin);131 freopen("luogu2486.out","w",stdout);132 #endif133 int x, y, z; char opt[5];134 read(n), read(q);135 for(int i=1;i<=n;i++) read(cl[i]);136 for(int i=1;i