85pts求调
查看原帖
85pts求调
988975
Owen1234楼主2024/7/20 20:18
#include <cstdio>
#include <stack>
//#define debug1
using namespace std;
int n,m;
struct Edge{
	int next;
	int to;
}es[200005];
int head[100005],ecnt;
void add_e(int u,int v){
	es[ecnt].next=head[u];
	es[ecnt].to=v;
	head[u]=ecnt;
	ecnt++;
}
struct node{
	int data;
	int l;
	int r;
}ns[100005*640];
int root[100005],ncnt;
inline int new_node(){
	ncnt++;
	return ncnt;
}
inline void pushup(int id){
	if(ns[id].l==0 && ns[id].r==0){
		ns[id].data=0;
	}
	else if(ns[id].l==0){
		ns[id].data=ns[ns[id].r].data;
	}
	else if(ns[id].r==0){
		ns[id].data=ns[ns[id].l].data;
	}
	else{
		ns[id].data=max(ns[ns[id].l].data,ns[ns[id].r].data);
	}
}
void add(int id,int l,int r,int wz,int zhi){
	#ifdef debug1
	printf("add_id:%d l:%d r:%d\n",id,l,r);
	#endif
	if(l==r){
		ns[id].data+=zhi;
		return;
	}
	int mid=(l+r)>>1;
	if(wz<=mid){
		if(ns[id].l==0){
			ns[id].l=new_node();
		}
		add(ns[id].l,l,mid,wz,zhi);
	}
	else{
		if(ns[id].r==0){
			ns[id].r=new_node();
		}
		add(ns[id].r,mid+1,r,wz,zhi);
	}
	pushup(id);
}
int ST_fa[100005][15],dep[100005];
void dfs1(int id,int fa){
	if(root[id]==0){
		root[id]=new_node();
	}
	for(int i=1;i<=14;i++) ST_fa[id][i]=ST_fa[ST_fa[id][i-1]][i-1];
	for(int i=head[id];i;i=es[i].next){
		int v=es[i].to;
		if(v==fa) continue;
		ST_fa[v][0]=id;
		dep[v]=dep[id]+1;
		dfs1(v,id);
	}
}
int LCA(int x,int y){
	if(dep[x]>dep[y]) swap(x,y); 
	for(int h=dep[y]-dep[x],i=0;h;h>>=1,i++){
		if(h&1) y=ST_fa[y][i];
	}
	if(x==y) return x;
	for(int i=14;i>=0;i--) if(ST_fa[x][i]!=ST_fa[y][i]) x=ST_fa[x][i],y=ST_fa[y][i];
	return ST_fa[x][0];
}
void merge(int idu,int idv,int l,int r){
	#ifdef debug1
	printf("merge_idu:%d merge_idv:%d l:%d r:%d\n",idu,idv,l,r);
	#endif
	if(l==r){
		ns[idv].data+=ns[idu].data;
		return;
	}
	int mid=(l+r)>>1;
	if(ns[idu].l!=0 && ns[idv].l==0){
		ns[idv].l=ns[idu].l;
	}
	else if(ns[idu].l!=0 && ns[idv].l!=0){
		merge(ns[idu].l,ns[idv].l,l,mid);
	}
	if(ns[idu].r!=0 && ns[idv].r==0){
		ns[idv].r=ns[idu].r;
	}
	else if(ns[idu].r!=0 && ns[idv].r!=0){
		merge(ns[idu].r,ns[idv].r,mid+1,r);
	}
	pushup(idv);
}
int ask(int id,int l,int r){
	#ifdef debug1
	printf("ask_id:%d l:%d r:%d\n",id,l,r);
	#endif
	if(l==r){
		if(ns[id].data==0){
			return 0;
		}
		return l;
	}
	int mid=(l+r)>>1;
	if(ns[id].l==0 && ns[id].r==0){
		return 0;
	}
	if(ns[id].l==0){
		return ask(ns[id].r,mid+1,r);
	}
	if(ns[id].r==0){
		return ask(ns[id].l,l,mid);
	}
	if(ns[ns[id].l].data>=ns[ns[id].r].data){
		return ask(ns[id].l,l,mid);
	}
	else{
		return ask(ns[id].r,mid+1,r);
	}
}
int ans[100005];
void dfs2(int id,int fa){
	//printf("dfs2:id:%d fa:%d\n",id,fa);
	for(int i=head[id];i;i=es[i].next){
		int v=es[i].to;
		if(v==fa){
			continue;
		}
		dfs2(v,id);
		merge(root[v],root[id],1,100000);
	}
	ans[id]=ask(root[id],1,100000);
}
int main(){
	ecnt=1;
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add_e(x,y);
		add_e(y,x);
	}
	dfs1(1,-1);
	for(int i=1;i<=m;i++){
		int x,y,z,lcaxy;
		scanf("%d%d%d",&x,&y,&z);
		lcaxy=LCA(x,y);
		add(root[x],1,100000,z,1);
		add(root[y],1,100000,z,1);
		add(root[lcaxy],1,100000,z,-1);
		if(ST_fa[lcaxy][0]!=0){
			add(root[ST_fa[lcaxy][0]],1,100000,z,-1);
		}
	}
	dfs2(1,-1);
	for(int i=1;i<=n;i++){
		printf("%d\n",ans[i]);
	}
	return 0;
}

2024/7/20 20:18
加载中...