清明梦超能力者黄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
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<<"----"<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<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<<"------"<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){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<<"------------"<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;
}

转载于:https://www.cnblogs.com/na7-TRZNDP-Z/p/9782438.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！