NC19813. 清明梦超能力者黄YY
描述
输入描述
第一行三个整数n, m, k，代表树的点数，黄YY染色的次数，以及最后求颜色时，倒数的次数（1 ≤ n, m, k ≤ 100000）。
接下来n - 1行，每行u, v代表u, v两点之间有一条边。这里保证1 ≤ u, v
≤ n，且无重边与自环，是一棵标准的树。
接下来m行，每一行三个数字u, v, c代表黄YY在第这次用c颜色的画笔从u涂到了v。
输出描述
一行$n$个数字，输出每个点倒数第$k$次染色时的颜色。如果本身不足$k$次，输出0。
示例1
输入:
3 3 2 1 2 2 3 1 2 1 2 3 2 1 3 3
输出:
1 2 2
说明:
对于点1在第一次和第三次染色的时候分别被染色为1, 3，倒数第二次的颜色就是1。C++14(g++5.4) 解法, 执行用时: 418ms, 内存消耗: 23012K, 提交时间: 2018-10-06 16:53:12
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<vector>
#define MAXN 200015
#define inf 102000000
using namespace std;
int K,tim,tot;
int dep[MAXN],son[MAXN],maxx[MAXN],maxp[MAXN],id[MAXN],Top[MAXN],fa[MAXN],top[MAXN];
int lazy[MAXN],size[MAXN],ls[MAXN],rs[MAXN],a[MAXN],b[MAXN],ans[MAXN],e[MAXN];
vector<int>g[MAXN];
struct node{int u,v,c;}p[MAXN];
void _build1(int x){
int i,u,v;
size[x]++;
for(i=0;i<g[x].size();i++){
v=g[x][i];
if(v==fa[x])continue;
fa[v]=x;
dep[v]=dep[x]+1;
_build1(v);
if(!son[x])son[x]=v;
else if(size[v]>size[son[x]])son[x]=v;
size[x]+=size[v];
}
}
void _build2(int x,int anc){
int i,v;
id[x]=++tim;
e[id[x]]=x;
Top[x]=anc;
if(son[x])_build2(son[x],anc);
for(i=0;i<g[x].size();i++){
v=g[x][i];
if(v!=fa[x]&&v!=son[x])_build2(v,v);
}
}
void _putdown(int x){
lazy[ls[x]]+=lazy[x];
lazy[rs[x]]+=lazy[x];
maxx[x]+=lazy[x];
lazy[x]=0;
}
void _updown(int x){
_putdown(ls[x]);
_putdown(rs[x]);
if(maxx[ls[x]]>=maxx[rs[x]]){
maxx[x]=maxx[ls[x]];
maxp[x]=maxp[ls[x]];
}
else{
maxx[x]=maxx[rs[x]];
maxp[x]=maxp[rs[x]];
}
}
void _build0(int l,int r){
int now=++tot;
a[now]=l; b[now]=r;
if(l==r){
maxx[now]=0;
maxp[now]=l;
return;
}
int mid=(l+r)>>1;
ls[now]=tot+1;
_build0(l,mid);
rs[now]=tot+1;
_build0(mid+1,r);
_updown(now);
}
void _change(int l,int r,int x,int d){
if(l<=a[x]&&b[x]<=r){
maxx[x]=d;
return;
}
_putdown(x);
int mid=(a[x]+b[x])>>1;
if(l<=mid)_change(l,r,ls[x],d);
if(r>mid)_change(l,r,rs[x],d);
_updown(x);
}
void _getans(int x,int color){
while(lazy[x]+maxx[x]==K){
ans[e[maxp[x]]]=color;
_change(maxp[x],maxp[x],1,-inf);
}
}
void _add(int l,int r,int x,int color){
if(l<=a[x]&&b[x]<=r){
lazy[x]++;
if(lazy[x]+maxx[x]==K)_getans(x,color);
return;
}
_putdown(x);
int mid=(a[x]+b[x])>>1;
if(l<=mid)_add(l,r,ls[x],color);
if(r>mid)_add(l,r,rs[x],color);
_updown(x);
}
int main(){
int n,m,i,x,y,u,v;
scanf("%d%d%d",&n,&m,&K);
for(i=1;i<n;i++){
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
_build1(1);
_build2(1,0);
_build0(1,n);
for(i=1;i<=m;i++)
scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].c);
for(i=m;i>=1;i--){
u=p[i].u; v=p[i].v;
while(Top[u]!=Top[v]){
if(dep[Top[u]]<dep[Top[v]])swap(u,v);
_add(id[Top[u]],id[u],1,p[i].c);
u=fa[Top[u]];
}
if(dep[u]>dep[v])swap(u,v);
_add(id[u],id[v],1,p[i].c);
}
for(i=1;i<=n;i++)
printf("%d ",ans[i]);
return 0;
}
/*
3 3 3
1 2
2 3
1 2 1
2 3 2
1 3 3
*/
C++11(clang++ 3.9) 解法, 执行用时: 250ms, 内存消耗: 13664K, 提交时间: 2018-10-06 13:24:46
#include<bits/stdc++.h>
using namespace std;
struct edge{
int d,nex;
}e[200010];
int n,m,K,w[100010],ww,a[100010],b[100010],xh[100010],c[100010],efree,q[100010],dep[100010],top[100010],siz[100010],son[100010],t[400010],ans[100010],f[100010],tag[400010];
#define add(x,y) e[++efree]=(edge){y,q[x]},q[x]=efree
void dfs(int x,int y){
siz[x]=1;dep[x]=dep[y]+1;
for(int i=q[x];i;i=e[i].nex)
if(e[i].d!=y){
f[e[i].d]=x;
dfs(e[i].d,x);siz[x]+=siz[e[i].d];
if(siz[e[i].d]>siz[son[x]])son[x]=e[i].d;
}
}
void dfs2(int x,int y,int t){
w[x]=++ww,xh[ww]=x,top[x]=t;
if(son[x])dfs2(son[x],x,t);
for(int i=q[x];i;i=e[i].nex)
if(e[i].d!=son[x]&&e[i].d!=y)dfs2(e[i].d,x,e[i].d);
}
#define pd(k) tag[k<<1]+=tag[k],tag[k<<1|1]+=tag[k],t[k<<1]+=tag[k],t[k<<1|1]+=tag[k],tag[k]=0
void fd(int k,int l,int r,int x){
if(l==r)return (void)(t[k]=-1e6,ans[xh[l]]=x);
if(tag[k])pd(k);
int mid=(l+r)>>1;
if(t[k<<1]==K)fd(k<<1,l,mid,x);
if(t[k<<1|1]==K)fd(k<<1|1,mid+1,r,x);
t[k]=max(t[k<<1],t[k<<1|1]);
}
void ins(int k,int nl,int nr,int l,int r,int x){
if(nl==l&&nr==r){
t[k]++,tag[k]++;
if(t[k]==K)fd(k,l,r,x);
return;
}
if(tag[k])pd(k);
int mid=(nl+nr)>>1;
if(r<=mid)ins(k<<1,nl,mid,l,r,x);
else if(l>mid)ins(k<<1|1,mid+1,nr,l,r,x);
else ins(k<<1,nl,mid,l,mid,x),ins(k<<1|1,mid+1,nr,mid+1,r,x);
t[k]=max(t[k<<1],t[k<<1|1]);
}
int main(){
scanf("%d%d%d",&n,&m,&K);
for(int i=1;i<n;i++){
int x,y;scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
dfs(1,0),dfs2(1,0,1);
for(int i=1;i<=m;i++)scanf("%d%d%d",a+i,b+i,c+i);
for(int i=m;i;i--){
int x=a[i],y=b[i];
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]])swap(x,y);
ins(1,1,n,w[top[y]],w[y],c[i]);y=f[top[y]];
}
if(dep[x]>dep[y])swap(x,y);
ins(1,1,n,w[x],w[y],c[i]);
}
for(int i=1;i<=n;i++)printf("%d ",ans[i]);
return 0;
}