10pts玄关求条
查看原帖
10pts玄关求条
752711
hateful_bug楼主2024/12/11 17:53
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,h[N],nx[N<<1],b[N<<1],tt,f[22][N],dep[N],root[N],tot,hd[N];
struct xds
{
	int ans,zd,lc,rc;
}t[N*30];
void zj(int x,int y)////////add jianbian
{
	b[++tt]=y;
	nx[tt]=h[x];
	h[x]=tt;
}
void dfs(int x,int fa)////// lca yuchuli
{
	f[0][x]=fa;
	dep[x]=dep[fa]+1;
	for(int i=h[x];i;i=nx[i])
	{
		int y=b[i];
		if(y==fa)
		continue;
		dfs(y,x);
	}
}
int lca(int x,int y)///////qiu lca
{
	if(dep[x]<dep[y])
	swap(x,y);
	for(int i=20;i>=0;i--)
	if(dep[x]>=dep[y])
	x=f[i][x];
	if(x==y)
	return x;
	for(int i=20;i>=0;i--)
	if(f[i][x]!=f[i][y])
	x=f[i][x],y=f[i][y];
	return f[0][x];
}
void push_up(int p)
{
	if(t[t[p].lc].zd>=t[t[p].rc].zd)
	t[p].zd=t[t[p].lc].zd,t[p].ans=t[t[p].lc].ans;
	else
	t[p].zd=t[t[p].rc].zd,t[p].ans=t[t[p].rc].ans;
}
int build()
{
	++tot;
	t[tot].ans=t[tot].zd=t[tot].lc=t[tot].rc=0;
	return tot;
}
void xg(int p,int l,int r,int x,int k)
{
	if(l==r)
	{
		t[p].zd+=k;
		t[p].ans=x;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
	{
		if(!t[p].lc)
//		t[p].lc=++tot;
		t[p].lc=build();
		xg(t[p].lc,l,mid,x,k);
	}
	else
	{
		if(!t[p].rc)
//		t[p].rc=++tot;
		t[p].rc=build();
		xg(t[p].rc,mid+1,r,x,k);
	}
	push_up(p);
}
int hb(int p,int q,int l,int r)
{
	if(!p) return q;
	if(!q) return p;
	if(l==r)
	{
		t[p].zd+=t[q].zd;
		return p;
	}
	int mid=(l+r)>>1;
	t[p].lc=hb(t[p].lc,t[q].lc,l,mid);
	t[p].rc=hb(t[p].rc,t[q].rc,mid+1,r);
	push_up(p);
	return p;
}
void dfs2(int x)
{
	for(int i=h[x];i;i=nx[i])
	{
		int y=b[i];
		if(y==f[0][x])
		continue;
		dfs2(y);
		root[x]=hb(root[x],root[y],0,1e5);
	}
	hd[x]=t[root[x]].ans;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		zj(x,y);zj(y,x);
	}
	dfs(1,0);
	for(int i=1;i<=20;i++)
	for(int j=1;j<=n;j++)
	f[i][j]=f[i-1][f[i-1][j]];/////lca ycl2
	for(int i=1;i<=n;i++)//////root csh........
	root[i]=build();
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		if(x==y)
		{
			xg(root[x],0,1e5,z,1);
			xg(root[f[0][x]],0,1e5,z,-1);
			continue;
		}
		int fa=lca(x,y);
		xg(root[x],0,1e5,z,1);
		xg(root[y],0,1e5,z,1);
		xg(root[fa],0,1e5,z,-1);
		xg(root[f[0][fa]],0,1e5,z,-1);/////////xg
	}
	dfs2(1);
	for(int i=1;i<=n;i++)////////hd
	printf("%d\n",hd[i]);
	return 0;
}
2024/12/11 17:53
加载中...