N个点，形成一个树状结构。有M次发放，每次选择两个点x,y
对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成
所有发放后，每个点存放最多的是哪种物品。
N个点，形成一个树状结构。有M次发放，每次选择两个点x,y
对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成
所有发放后，每个点存放最多的是哪种物品。
第一行数字N，M
接下来N-1行，每行两个数字a,b,表示a与b间有一条边
再接下来M行，每行三个数字x,y,z.如题
输出有N行
每i行的数字表示第i个点存放最多的物品是哪一种，如果有
多种物品的数量一样，输出编号最小的。如果某个点没有物品
则输出0
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int h[100010];
int root[100010];
int ls[6000010];
int rs[6000010];
int next[200010];
int head[100010];
int to[200010];
int f[100010][18];
int d[100010];
int sum[6000010];
int ans[100010];
int tot;
int x,y;
int n,m;
int num;
int cnt;
struct miku
{
int x;
int y;
int z;
}a[100010];
void add(int x,int y)
{
tot++;
next[tot]=head[x];
head[x]=tot;
to[tot]=y;
}
void dfs(int x)
{
d[x]=d[f[x][0]]+1;
for(int i=1;i<=17;i++)
{
f[x][i]=f[f[x][i-1]][i-1];
}
for(int i=head[x];i;i=next[i])
{
if(to[i]!=f[x][0])
{
f[to[i]][0]=x;
dfs(to[i]);
}
}
}
int lca(int x,int y)
{
if(d[x]<d[y])
{
swap(x,y);
}
int dep=d[x]-d[y];
for(int i=0;i<=17;i++)
{
if((dep&(1<<i)))
{
x=f[x][i];
}
}
if(x==y)
{
return x;
}
for(int i=17;i>=0;i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
void updata(int rt)
{
if(ls[rt]&&rs[rt])
{
sum[rt]=max(sum[ls[rt]],sum[rs[rt]]);
}
else if(ls[rt])
{
sum[rt]=sum[ls[rt]];
}
else if(rs[rt])
{
sum[rt]=sum[rs[rt]];
}
}
void insert(int &rt,int l,int r,int k,int v)
{
if(!rt)
{
rt=++cnt;
}
if(l==r)
{
sum[rt]+=v;
return ;
}
int mid=(l+r)>>1;
if(k<=mid)
{
insert(ls[rt],l,mid,k,v);
}
else
{
insert(rs[rt],mid+1,r,k,v);
}
updata(rt);
}
void merge(int &rt,int x)
{
if(!rt||!x)
{
rt=rt+x;
return ;
}
sum[rt]+=sum[x];
merge(ls[rt],ls[x]);
merge(rs[rt],rs[x]);
updata(rt);
}
int query(int rt,int l,int r)
{
int mid=(l+r)>>1;
if(l==r)
{
if(sum[rt]>0)
{
return l;
}
return 0;
}
if(sum[ls[rt]]>=sum[rs[rt]])
{
return query(ls[rt],l,mid);
}
else
{
return query(rs[rt],mid+1,r);
}
}
void downdata(int x)
{
for(int i=head[x];i;i=next[i])
{
if(to[i]!=f[x][0])
{
downdata(to[i]);
merge(root[x],root[to[i]]);
}
}
ans[x]=query(root[x],1,num);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs(1);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
h[i]=a[i].z;
}
sort(h+1,h+1+m);
num=unique(h+1,h+1+m)-h-1;
for(int i=1;i<=m;i++)
{
int anc=lca(a[i].x,a[i].y);
a[i].z=lower_bound(h+1,h+1+num,a[i].z)-h;
insert(root[a[i].x],1,num,a[i].z,1);
insert(root[a[i].y],1,num,a[i].z,1);
insert(root[anc],1,num,a[i].z,-1);
if(anc!=1)
{
insert(root[f[anc][0]],1,num,a[i].z,-1);
}
}
downdata(1);
for(int i=1;i<=n;i++)
{
printf("%d\n",h[ans[i]]);
}
}
原文：https://www.cnblogs.com/Khada-Jhin/p/9740501.html