[Ispc2009]Let there be rainbows!

Description

HY Star是一个处处充满和谐，人民安居乐业的星球，但是HYStar却没有被评上宇宙文明星球，很大程度上是因为星球的形象问题。
HY Star由N个国家组成,并且在一些国家之间修建了道路以方便交流。由于HY Star是一个和谐的
星球，因此任意两个国家有且仅有一条路径连接它们。而让HYStar备受诟病的便是他们修建的道路的颜色过于单调,全部是使用灰色。
经过了一年又一年的宇宙文明星球的落选,HY Star的首领BOSS决定改变这种状况，但是他并
不想重新修建新的道路，因为这太耗费人力物力,他决定将已有的道路重新涂色。在各方的讨论下，BOSS决定将现有的道路涂成彩虹的颜色。每一天,BOSS都会选择两个国家A,B和一种颜色C，并将A,B之间颜色不是C的道路的颜色都涂成C。
BOSS将涂色的具体计划预先告诉了颜料厂，以便有充足的时间来准备颜料。作为颜料厂的负责人,你需要知道每种颜色被使用了多少次。

Input

第一行,一个整数N,表示HY Star的国家的编号是1~N。
下面若干行，每行两个数A,B,表示A,B之间有道路直接连接。
下面一行,一个整数Q,表示计划的持续天数。
下面Q行,每行三个正整数,S,T,C(1<=S,T<=N,1<=C<=7),表示将S,T之间颜色不是C的道路的颜色都涂成C。
1 < = N,Q < = 200000

Output

共包含7行,第i行包含一个整数，表示颜色i的使用次数。

Sample Input:

4
1 2
2 3
3 4
3
1 4 1
2 4 2
1 3 1

Out put:

4
2
0
0
0
0
0

Solution:

本题可以用树链剖分来解决，线段树的维护方法有两种：
每个区间记录7个颜色的值，每个区间记录当前颜色值
第一种方法我们不在此讨论，我们来讲第二种方法
若当前区间的颜色为同一种，则记录这种颜色，否则为0
每次更新之前，就把这条区间长度减去原有的颜色数量，在把答案加到数组里去就行了
更新时就按照普通线段树来更新，要注意的是，本题细节很重要

Code:

#include<bits/stdc++.h>
#define N 2000001
#define inf 19260817
#define ls q<<1
#define rs q<<1|1
using namespace std;
int n,m,tl,ans[10];
int fa[N],top[N],son[N],sz[N],dep[N];
int cnt,seg[N],tag[N<<2];
int tot,head[N],nxt[N<<1],to[N<<1];
void ins(int x,int y){
    nxt[++tot]=head[x];
    to[tot]=y;head[x]=tot;
}
void update(int q){tag[q]=(tag[ls]==tag[rs])?tag[ls]:0;}
void pushdown(int q,int l,int r){
    if(!tag[q])return ;
    tag[ls]=tag[rs]=tag[q];
}
void change(int q,int l,int r,int L,int R,int v){
    if(tag[q]==v)return ;
    if(l>=L&&r<=R){
        tag[q]=v;
        return ;
    }
    pushdown(q,l,r);
    int mid=(l+r)>>1;
    if(mid>=L)change(ls,l,mid,L,R,v);
    if(mid<R)change(rs,mid+1,r,L,R,v);
    update(q);
}
int query(int q,int l,int r,int L,int R,int col){
    if(l>=L&&r<=R&&tag[q]==col)return r-l+1;
    if(tag[q]!=0&&tag[q]!=col)return 0;
    if(l==r)return 0;
    pushdown(q,l,r);
    int mid=(l+r)>>1,res=0;
    if(mid>=L)res+=query(ls,l,mid,L,R,col);
    if(mid<R)res+=query(rs,mid+1,r,L,R,col);
    return res;
}
void dfs1(int x,int f){
    int mxsz=0;
    fa[x]=f;dep[x]=dep[f]+1;sz[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(y==f)continue;
        dfs1(y,x);sz[x]+=sz[y];
        if(sz[y]>mxsz)son[x]=y,mxsz=sz[y];
    }
}
void dfs2(int x,int topx){
    seg[x]=++cnt;top[x]=topx;
    if(!son[x])return ; 
    if(son[x])dfs2(son[x],topx);
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(y==fa[x]||y==son[x])continue;
        dfs2(y,y);
    }
}
int Query(int x,int y,int col){
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        ans+=query(1,1,n,seg[top[x]],seg[x],col);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    ans+=query(1,1,n,seg[x]+1,seg[y],col);
    return ans;
}
int Tot(int x,int y){
    int t=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        t+=seg[x]-seg[top[x]]+1;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    t+=seg[y]-seg[x];
    return t;
}
void Change(int x,int y,int col){
    int lst=Query(x,y,col);
    int xx=x,yy=y;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        change(1,1,n,seg[top[x]],seg[x],col);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    change(1,1,n,seg[x]+1,seg[y],col);
    ans[col]+=Tot(xx,yy)-lst;
}
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main(){
    n=read();
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        ins(x,y);ins(y,x);
    }
    m=read();dfs1(1,0);dfs2(1,1);
    for(int i=1;i<=m;i++){
        int x=read(),y=read(),col=read();
        Change(x,y,col);
    }
    for(int i=1;i<=7;i++)printf("%d\n",ans[i]);
    return 0;
}