线段树合并15pts求调玄关
查看原帖
线段树合并15pts求调玄关
496117
wyh0721楼主2024/12/7 10:03
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;
int dep[500005],f[500005][105],lg[500005];
vector <int> v[500005];
int ans[500005];
int rt[500005],sum[500005],res[500005],ls[500005],rs[500005];
void dfs(int x,int fa)
{
	f[x][0]=fa;
	dep[x]=dep[fa]+1;
	for(int i=1;i<lg[dep[x]];i++)
		f[x][i]=f[f[x][i-1]][i-1];
	for(int i=0;i<v[x].size();i++)
		if(v[x][i]!=fa)
			dfs(v[x][i],x); 
}
int LCA(int x,int y)
{
	if(dep[x]<dep[y])
		swap(x,y);
	if(dep[x]>dep[y])
		x=f[x][lg[dep[x]-dep[y]]-1];
	if(x==y)
		return x;
	for(int i=lg[dep[x]]-1;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0]; 
}
void update(int x)
{
	if(sum[ls[x]]<sum[rs[x]])
	{
		res[x]=res[rs[x]];
		sum[x]=sum[rs[x]]; 
	}
	else
	{
		res[x]=res[ls[x]];
		sum[x]=sum[ls[x]];
	}
}
int add(int id,int x,int y,int co,int val)
{
	if(!id)
		id=++cnt;
	if(x==y)
	{
		sum[id]+=val;
		res[id]=co;
		return id;
	}
	int mid=(x+y)>>1;
	if(co<=mid)
		ls[id]=add(ls[id],x,mid,co,val);
	else
		rs[id]=add(rs[id],mid+1,y,co,val);
	update(id);
	return id;
}
int merge(int a,int b,int x,int y)
{
	if(!a || !b)
		return a+b;
	if(x==y)
	{
		sum[a]+=sum[b];
		return a;
	}
	int mid=(x+y)>>1;
	ls[a]=merge(ls[a],ls[b],x,mid);
	rs[a]=merge(rs[a],rs[b],mid+1,y);
	update(a);
	return a; 
}
void calc(int x)
{
	for(int i=0;i<v[x].size();i++)
	{
		if(v[x][i]==f[x][0])
			continue;
		calc(v[x][i]);
		rt[x]=merge(rt[x],rt[v[x][i]],1,100000);
	}
	ans[x]=res[rt[x]];
	if(sum[rt[x]]==0)
		ans[x]=0;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x); 
	} 
	for(int i=1;i<=n;i++)
		lg[i]=lg[i/2]+1;
	dfs(1,0);
	while(m--)
	{
		int x,y,z;
		cin>>x>>y>>z;
		int lc=LCA(x,y);
		rt[x]=add(rt[x],1,100000,z,1);
		rt[y]=add(rt[y],1,100000,z,1);
		rt[lc]=add(rt[lc],1,100000,z,-1);
		rt[f[lc][0]]=add(rt[f[lc][0]],1,100000,z,-1);
	}
	calc(1);
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<endl;
    return 0;
}

2024/12/7 10:03
加载中...