[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;

}

巴特西