蒟蒻RE求助
查看原帖
蒟蒻RE求助
101042
zhz小蒟蒻楼主2020/8/21 20:14

不知道为什么 RERE 了,并且在本地和洛谷 IDEIDE 都可以正常运行

#include <iostream>
#include <cstdio>
#include <vector>
#define N 100011
#define ls tr[k].l
#define rs tr[k].r
using namespace std;
struct Node
{
	int l;
	int r;
	int sum;  //数量 
	int ans;  //颜色 
}tr[N<<5];
int rt[N<<5],dep[N],ans_sum[N],fa[N][22],cnt;
vector<int>T[N];
void push_up(int k)
{
	if(tr[ls].sum>tr[rs].sum)
	{
		tr[k].sum=tr[ls].sum;
		tr[k].ans=tr[ls].ans;
	}
	if(tr[rs].sum>tr[ls].sum)
	{
		tr[k].sum=tr[rs].sum;
		tr[k].ans=tr[rs].ans;
	}
	if(tr[ls].sum==tr[rs].sum)
	{
		tr[k].sum=tr[ls].sum;
		tr[k].ans=min(tr[ls].ans,tr[rs].ans);
	}
}
int update(int &now,int l,int r,int pos,int v)
{
	if(!now) now=++cnt;
	if(l==r)
	{
		tr[now].sum+=v;
		tr[now].ans=l;
		return 0;
	}
	int mid=(l+r)>>1;
	if(pos<=mid) update(tr[now].l,l,mid,pos,v);
	else update(tr[now].r,mid+1,r,pos,v);
	push_up(now);
}
int merge(int a,int b,int l,int r)
{
	if(!a) return b;
	if(!b) return a;
	if(l==r)
	{
		tr[a].sum+=tr[b].sum;
		tr[a].ans=l;
		return a;
	}
	int mid=(l+r)>>1;
	tr[a].l=merge(tr[a].l,tr[b].l,l,mid);
	tr[a].r=merge(tr[a].r,tr[b].r,mid+1,r);
	push_up(a);
	return a;
}
void dfs(int u,int f)
{
	dep[u]=dep[f]+1;
	fa[u][0]=f;
	for(int i=1;(1<<i)<=dep[u];++i) fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=0;i<T[u].size();++i)
	{
		int v=T[u][i];
		if(v==f) continue;
		dfs(v,u);
	}
}
int LCA(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=21;i>=0;--i) 
		if(dep[fa[x][i]]>=dep[y])
			x=fa[x][i];
	if(x==y) return x;
	for(int i=21;i>=0;--i)
		if(fa[x][i]!=fa[y][i])
		{
			x=fa[x][i];
			y=fa[y][i];
		}
	return fa[x][0];
}
void get_ans(int u,int f)
{
	for(int i=0;i<T[u].size();++i)
	{
		int v=T[u][i];
		if(v==f) continue;
		get_ans(v,u);
		merge(rt[u],rt[v],1,N);
	}
	ans_sum[u]=tr[rt[u]].ans;
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i) rt[i]=i,++cnt;
	for(int i=1;i<n;++i)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		T[x].push_back(y);
		T[y].push_back(x);
	} 
	dfs(1,0);
	for(int i=1;i<=m;++i)
	{
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		int A=LCA(x,y);
		update(rt[x],1,N,z,1);
		update(rt[y],1,N,z,1);
		update(rt[A],1,N,z,-1);
		update(rt[fa[A][0]],1,N,z,-1);
	} 
	get_ans(1,0);
	for(int i=1;i<=n;++i) printf("%d\n",ans_sum[i]); 
	return 0;
}
2020/8/21 20:14
加载中...