[文章目录]
Description
N个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成所有发放后，每个点存放最多的是哪种物品。n,m<=10^5 z<=10^9
对于每个点建造维护种类个数的权值线段树，对于每次发放进行差分x,y+z,lca fa[lca]-z，之后到每个节点权值线段树合并+修改。
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000
#define mp(x,y) make_pair(x,y)
#define pb push_back
int n,m,v1[N],v2[N],col[N],b[N],c[N],tot;
int head[N],to[N<<1],nxt[N<<1],cnt;
inline int getid(int x){return lower_bound(c+1,c+tot+1,x)-c;}
inline void add(int x,int y)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
int Log[N],fa[N][18],dep[N],ran[N],tim;
void dfs(int x,int pre)
{
for(int i=1;i<=Log[dep[x]];++i) fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
{
fa[to[i]][0]=x; dep[to[i]]=dep[x]+1;
dfs(to[i],x);
}
ran[++tim]=x;
}
int getlca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
int z=dep[x]-dep[y];
while(z) x=fa[x][Log[-z&z]],z-=-z&z;
if(x==y) return x;
for(int i=Log[dep[x]];~i;--i)
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
vector<pair<int,int> >ve[N];
int se,ans[N],rot[N];
queue<int>del;
struct seg
{
int ls,rs,w,s;
}s[N*40];
inline void newseg(int &x)
{
if(!del.empty()) x=del.front(),del.pop();
else x=++se;
}
inline void pushup(int x)
{
if(s[s[x].rs].s>s[s[x].ls].s) s[x].s=s[s[x].rs].s,s[x].w=s[s[x].rs].w;
else s[x].s=s[s[x].ls].s,s[x].w=s[s[x].ls].w;
}
void update(int l,int r,int &x,int y,int z,int w)
{
newseg(x);
if(l==r)
{
s[x].ls=s[x].rs=0; s[x].w=l;
s[x].s=s[y].s+w;
return ;
}
int mid=(l+r)>>1;
if(z<=mid) s[x].rs=s[y].rs,update(l,mid,s[x].ls,s[y].ls,z,w);
else s[x].ls=s[y].ls,update(mid+1,r,s[x].rs,s[y].rs,z,w);
pushup(x); if(y) del.push(y);
}
int merge(int x,int y,int l,int r)
{
if(!x||!y) return x|y;
if(l==r)
{
s[x].s+=s[y].s;
del.push(y);
return x;
}
int mid=(l+r)>>1;
s[x].ls=merge(s[x].ls,s[y].ls,l,mid);
s[x].rs=merge(s[x].rs,s[y].rs,mid+1,r);
pushup(x); del.push(y); return x;
}
int main()
{
scanf("%d%d",&n,&m); int i,x,y;
for(i=1;i<n;++i)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
for(i=2;i<=n;++i) Log[i]=Log[i>>1]+1;
dfs(1,0);
for(i=1;i<=m;++i)
{
scanf("%d%d%d",v1+i,v2+i,col+i);
b[i]=col[i];
}
sort(b+1,b+m+1); c[++tot]=b[1];
for(i=2;i<=m;++i) if(b[i]!=b[i-1]) c[++tot]=b[i];
for(i=1;i<=m;++i)
{
x=getlca(v1[i],v2[i]); y=getid(col[i]);
ve[v1[i]].pb(mp(y,1)); ve[v2[i]].pb(mp(y,1));
ve[x].pb(mp(y,-1)); ve[fa[x][0]].pb(mp(y,-1));
}
for(i=1;i<=n;++i)
{
x=ran[i];
for(int j=head[x];j;j=nxt[j]) if(to[j]!=fa[x][0])
rot[x]=merge(rot[x],rot[to[j]],1,tot);
for(int j=0;j<(int)ve[x].size();++j)
update(1,tot,rot[x],rot[x],ve[x][j].first,ve[x][j].second);
ans[x]=s[rot[x]].s ? c[s[rot[x]].w] : 0;
}
for(i=1;i<=n;++i) printf("%d\n",ans[i]);
return 0;
}