清明梦超能力者黄YY

传送门

题目：

黄YY是一个清明梦超能力者，同时也是一个记忆大师。他能够轻松控制自己在梦中的一切，在醒来之后还能清晰的记得梦中所有的细节，这让他的朋友们都十分羡慕。
又是一个晚上，黄YY又到了自己的梦中，并且随手造出了一棵有n个点的树，树上每个点有一个初始颜色0。为了让这棵树不那么单调，黄YY拿起了画笔在上面尽情上色。每一次上色可以用u,
v, c来描述，代表黄YY把u, v这条路径上的点都染色成了c。
正当黄YY开心的完成了m次染色，准备在早上醒来之时向朋友们炫耀。但现实中的黄YY由于过于兴奋滚到了床下，撞到了脑袋，在剧痛中醒来。由于脑部受到了严重创伤，黄YY对刚才梦境中发生的一切发生了严重的信息丢失。
但英俊潇洒的黄YY当然不希望自己的窘态被朋友们发现。为了证明自己还是那个清明梦超能力者，他希望告诉朋友们自己上色后每个节点的颜色。同时为了更进一步证明他还是个记忆大师，他希望干脆直接说出每个点在倒数第k次染色时的颜色。
当然，现在的黄YY已经成了弱智了，作为黄YY最亲密的朋友，你快来帮帮黄YY吧！

题解：

这题可以用树链剖分做。染色的时候就用树链剖分修改操作。因为是要求倒数第K次的染色情况，因此我们可以倒着染色，然后初始化染色次数为K，每次操作就K–，并用线段树维护区间最小值，一旦出现最小值就把这个点加到答案上。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
const int inf=0x3f3f3f;
struct edge
{
	int next,to;
}e[maxn<<1];
int head[maxn],cnt;
void add(int u,int v)
{
	cnt++;
	e[cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
int siz[maxn],fa[maxn],son[maxn],rnk[maxn],dep[maxn],num[maxn],top[maxn],tot;

void dfs1(int u)
{
	siz[u]=1;
	for(int i=head[u];i;i=e[i].next)
	{
//		cout<<"----"<<endl;
		if(e[i].to==fa[u])continue;
		dep[e[i].to]=dep[u]+1;
		fa[e[i].to]=u;
		dfs1(e[i].to);
		siz[u]+=siz[e[i].to];
		if(siz[e[i].to]>siz[son[u]]) son[u]=e[i].to;
	}
 } 
void dfs2(int x,int tp)
{
	top[x]=tp;
	num[x]=++tot;
	rnk[tot]=x;
	if(son[x])dfs2(son[x],tp);
	for(int i=head[x];i;i=e[i].next)
		if(e[i].to!=fa[x]&&e[i].to!=son[x])
			dfs2(e[i].to,e[i].to); 
}
struct node
{
	int l,r,c;
}opt[maxn];

int tree[maxn<<1],ls[maxn<<1],rs[maxn<<1],lz[maxn<<1],trtot;
int ans[maxn],Color;
int n,m,K;

void pushup(int k,int l,int r)
{
	if(l==r)return;
	tree[k]=min(tree[ls[k]],tree[rs[k]]);
}
void pushdown(int k,int l,int r)
{
	if(l==r)return;
	if(!lz[k])return;
	int ff=lz[k],ll=ls[k],rr=rs[k];
	tree[ll]-=ff,tree[rr]-=ff;
	lz[ll]+=ff,lz[rr]+=ff,lz[k]=0;
}
void build(int k,int l,int r)
{
	if(l==r)
	{
		tree[k]=K;
		return;
	}
	int mid=(l+r)>>1;
	ls[k]=++trtot;
	rs[k]=++trtot;
	build(ls[k],l,mid);
	build(rs[k],mid+1,r);
	pushup(k,l,r);
}
void change(int k,int l,int r,int x,int y)
{
	pushdown(k,l,r);
//	cout<<k<<" "<<ls[k]<<" "<<rs[k]<<endl;
	if(l==x&&r==y)
	{
		tree[k]--,lz[k]++;
		return;
	}
	int mid=(l+r)>>1;
	if(y<=mid) 
		change(ls[k],l,mid,x,y);
	else if(x>mid) 
		change(rs[k],mid+1,r,x,y);
	else change(ls[k],l,mid,x,mid),change(rs[k],mid+1,r,mid+1,y);
	pushup(k,l,r);
}
void modify(int k,int l,int r)
{
	pushdown(k,l,r);
	if(l==r&&tree[k]==0)
	{
		tree[k]=inf;
		ans[rnk[l]]=Color;
		return;
	}
	int mid=(l+r)>>1;
	if(!tree[ls[k]]) modify(ls[k],l,mid);
	if(!tree[rs[k]]) modify(rs[k],mid+1,r);
	pushup(k,l,r);
}
void update_path(int x,int y,int c)
{
	Color = c;
	int xx=top[x],yy=top[y];
	while(xx!=yy)
	{
//		cout<<"------"<<endl;
		if(dep[xx]>dep[yy])
		{
			change(1,1,n,num[xx],num[x]);
			x=fa[xx];
		}
		else
		{
			change(1,1,n,num[yy],num[y]);
			y=fa[yy];
		}
		xx=top[x];
		yy=top[y];
	}
	if(x!=y)
	{
		if(num[x]>num[y])swap(x,y);
		change(1,1,n,num[x],num[y]);
	}
	else change(1,1,n,num[x],num[x]);
	modify(1,1,n);
}
int main()
{
	cin>>n>>m>>K;
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	dfs1(1);
	dfs2(1,1);
	trtot=1;
	build(1,1,n);
//	cout<<"------------"<<endl;
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&opt[i].l,&opt[i].r,&opt[i].c);
	
	for(int i=m;i;i--)
		update_path(opt[i].l,opt[i].r,opt[i].c);
	for(int i=1;i<=n;i++)
		printf("%d%c",ans[i],i==n?'\n':' ');
	return 0;
}

Q.E.D.