求求了,帮帮孩子吧
查看原帖
求求了,帮帮孩子吧
752774
KAxdd楼主2023/11/1 17:16
#include<bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
int head[200005],nxt[200005],to[200005],tot,dep[100005],vis[100005];
int rot[200005],sum[8000005],ls[8000005],rs[8000005],tre[8000005],cnt=0,ans[100005];
int fa[4000005],son[4000005],id[4000005],siz[200005],tmp,top[200005];
void add(int x,int y) {
	to[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
}
void dfs1(int x,int faa) {
	fa[x]=faa;
	siz[x]=1;
	dep[x]=dep[faa]+1;
	for(int i=head[x];i;i=nxt[i]) {
		if(to[i]==faa) continue;
		dfs1(to[i],x);
		siz[x]+=siz[to[i]];
		if(siz[to[i]]>siz[son[x]]) son[x]=to[i];
	}
}
void dfs2(int x,int topf) {
	id[x]=++tmp;
	top[x]=topf;
	if(!son[x]) return ;
	dfs2(son[x],topf);
	for(int i=head[x];i;i=nxt[i]) {
		if(son[x]==to[i] || to[i]==fa[x]) continue;
		dfs2(to[i],to[i]);
	}
}
void pushup(int x) {
	if(ls[x]==0 ) {
		sum[x]=sum[rs[x]];
		tre[x]=tre[rs[x]];
		return ;
	} else if(rs[x]==0) {
		sum[x]=sum[ls[x]];
		tre[x]=tre[ls[x]];
		//printf("%d %d\n",x,tre[x]);
		return ;
	}
	if(sum[ls[x]]>=sum[rs[x]]) {
		sum[x]=sum[ls[x]];
		tre[x]=tre[ls[x]];
	} else {
		sum[x]=sum[rs[x]];
		tre[x]=sum[rs[x]];
	}
}
void change(int &x,int l,int r,int pos,int tmp) {
	if(x==0) x=++cnt;
	if(l==r) {
		sum[x]+=tmp;
		tre[x]=pos;
		return ;
	}
	if(pos<=mid) change(ls[x],l,mid,pos,tmp);
	else change(rs[x],mid+1,r,pos,tmp);
	pushup(x);
}
int merge(int a,int b,int l,int r) {
	if(a==0 || b==0) return a+b;
	if(l==r) {
		sum[a]+=sum[b];
		return a;
	}
	merge(ls[a],ls[b],l,mid);
	merge(rs[a],rs[b],mid+1,r);
	pushup(a);
	return a;
} 
void calc(int x,int fa) {
	for(int i=head[x];i;i=nxt[i]) {
		int v=to[i];
		if(v==fa) continue;
		calc(v,x);
		rot[x]=merge(rot[x],rot[v],1,100000);
	}
	ans[x]=tre[rot[x]];
	if(sum[rot[x]]==0) ans[x]=0;
}
int lca(int x,int y) {
	while(top[x]!=top[y]) {
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	return x;
}
int main() {
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<n;i++) {
		int x,y;
		scanf("%d %d",&x,&y);
		add(x,y); add(y,x);
	}
	dfs1(1,0);
	dfs2(1,1);
	while(m--) {
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		change(rot[x],1,100000,z,1);
		change(rot[y],1,100000,z,1);
		change(rot[lca(x,y)],1,100000,z,-1);
		change(rot[fa[lca(x,y)]],1,100000,z,-1);
	}
	calc(1,0);
	for(int i=1;i<=n;i++) {
		printf("%d\n",ans[i]);
	}
	return 0;
} 
/*
10 10 
2 1 
3 2 
4 3 
5 3 
6 3 
7 4 
8 5 
9 8 
10 3 
6 2 6 
3 2 6 
3 3 2 
6 6 6 
10 3 3 
10 7 1 
3 7 4 
7 9 5 
4 2 4 
3 3 6

*/

没有输入1,莫名其妙出现了1

2023/11/1 17:16
加载中...