萌新WA 15pts求助
查看原帖
萌新WA 15pts求助
519276
W_Sibo楼主2024/10/4 16:39
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
int n,m,fa[N][20],dep[N],lg[N],tot=0,ans1[N];
vector<int> v[N];
inline void output(int p,int root,int rt2);
struct tree{
	int l,r,ma,v,lc,rc;
}tr[80*N];
inline void lginit(){
	lg[1]=0;
	for(int i=2;i<=n;i++){
		lg[i]=lg[i>>1]+1;
	}
}
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
	return x*f;
}
inline void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
inline void dfsbt(int x,int fath){
	dep[x]=dep[fath]+1;
	fa[x][0]=fath;
	for(int i=1;i<=lg[dep[x]];i++){
		fa[x][i]=fa[fa[x][i-1]][i-1];
	}
	for(auto i:v[x]){
		if(fa[x][0]==i) continue;
		dfsbt(i,x); 
	}
}
inline int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=lg[dep[x]];i>=0;i--){
		if(dep[fa[x][i]]<dep[y]) continue;
		x=fa[x][i];
	}
	if(x==y) return x;
	for(int i=lg[dep[x]];i>=0;i--){
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}
inline void buildroot(){
	for(int i=1;i<=n;i++){
		tr[++tot].l=1;
		tr[tot].r=1e5;
	}
}
inline void pushup(int p){
	if(tr[tr[p].lc].v>tr[tr[p].rc].v){
		tr[p].ma=tr[tr[p].lc].ma;
		tr[p].v=tr[tr[p].lc].v;
	}else if(tr[tr[p].lc].v<tr[tr[p].rc].v){
		tr[p].ma=tr[tr[p].rc].ma;
		tr[p].v=tr[tr[p].rc].v;
	}else{
		tr[p].ma=min(tr[tr[p].lc].ma,tr[tr[p].rc].ma);
		tr[p].v=tr[tr[p].rc].v;
	}
}
inline void update(int p,int x,int v){
	if(!p) return;
	//cout<<p<<'|';
	if(tr[p].l==tr[p].r){
		tr[p].ma=x;
		tr[p].v+=v;
		//cout<<p<<' ';
		return;
	}
	int mid=(tr[p].l+tr[p].r)>>1;
	if(x<=mid){
		if(!tr[p].lc){
			tr[p].lc=++tot;
			tr[tot].l=tr[p].l;
			tr[tot].r=mid;
			//cout<<tot<<' '<<tr[p].l<<' '<<mid<<'\n';
		}
		update(tr[p].lc,x,v);
	}
	if(x>mid){
		if(!tr[p].rc){
			tr[p].rc=++tot;
			tr[tot].l=mid+1;
			tr[tot].r=tr[p].r;
			//cout<<tot<<' '<<mid+1<<' '<<tr[p].r<<'\n';
		}
		update(tr[p].rc,x,v);
	}
	pushup(p);
}
inline void merge(int &p,int q,int o,int s){
	if(!q) return;
	if(!p){
		p=++tot;
		tr[p]=tr[q];
		return;
	}
	if(tr[p].l==tr[p].r){
		update(o,tr[p].l,tr[q].v);
	}
		merge(tr[p].lc,tr[q].lc,o,s);
		merge(tr[p].rc,tr[q].rc,o,s);
}
inline void output(int p,int root,int rt2){
	cout<<rt2<<"->"<<root<<':'<<p<<' '<<tr[p].ma<<' '<<tr[p].v<<' '<<tr[p].l<<' '<<tr[p].r<<'\n';
	if(tr[p].lc) output(tr[p].lc,root,rt2);
	if(tr[p].rc) output(tr[p].rc,root,rt2);
}
inline void dfs(int x,int fath){
	for(auto i:v[x]){
		if(i==fath) continue;
		dfs(i,x);
		//output(x,x,0);
		//output(i,i,0);
		merge(x,i,x,i);
		//output(x,i,x);
	}
	pushup(x);
	ans1[x]=tr[x].v==0?0:tr[x].ma;
}
signed main(){
	freopen("P4556_3.in","r",stdin);
	n=read();
	m=read();
	lginit();
	for(int i=1;i<n;i++){
		int x=read(),y=read();
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfsbt(1,0);
	buildroot();
	for(int i=1;i<=m;i++){
		int x=read(),y=read(),z=read();
		update(fa[lca(x,y)][0],z,-1);
		update(lca(x,y),z,-1);
		update(x,z,1);
		update(y,z,1);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++){
		write(ans1[i]);
		putchar(10);
	}
}
2024/10/4 16:39
加载中...