萌新求助线段树合并不过样例
查看原帖
萌新求助线段树合并不过样例
253936
simonG楼主2022/8/14 20:59
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1e5+10;
int tot,head[N],ver[2*N],nxt[2*N];
int lc[32*N],rc[32*N],d[32*N],t[32*N];
int top[N],fa[N],deep[N],son[N],sum[N],qx[N],qy[N],qz[N],ans[N];
int n,m,rt[N],cnt,R,num;
void addedge(int x,int y) {
	ver[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
}
void dfs1(int u) {
	sum[u]=1; int maxx=-1;
	for(int i=head[u]; i; i=nxt[i]) {
		int v=ver[i];
		if(!deep[v]) {
			deep[v]=deep[u]+1; fa[v]=u;
			dfs1(v); sum[u]+=sum[v];
			if(sum[v]>maxx) {maxx=sum[v]; son[u]=v;}
		}
	}
}
void dfs2(int u,int topf) {
	top[u]=topf;
	if(!son[u]) return ;
	dfs2(son[u],topf);
	for(int i=head[u]; i; i=nxt[i]) {
		int v=ver[i];
		if(!top[v]) dfs2(v,v);
	}
}
int lca(int u,int v) {
	while(top[u]!=top[v]) {
		if(deep[top[u]]<deep[top[v]]) swap(u,v);
		u=fa[top[u]];
	}
	if(deep[u]<deep[v]) return u;
	else return v;
}
void pushup(int p) {
	if(d[lc[p]]>=d[rc[p]]) {
		d[p]=d[lc[p]]; t[p]=t[lc[p]];
	} else {
		d[p]=d[rc[p]]; t[p]=t[rc[p]];
	}
}
int modify(int p,int x,int y,int pos,int val) {
	if(!p) p=++cnt;
	if(x==y) {d[p]+=val; t[p]=x; return p;}
	int mid=(x+y)/2;
	if(pos<=mid) lc[p]=modify(lc[p],x,mid,pos,val);
	else rc[p]=modify(rc[p],mid+1,y,pos,val);
	pushup(p);
	return p;
}
int merge(int p,int q,int x,int y) {
	if(!p) return q;
	if(!q) return p;
	if(x==y) {return d[p]+=d[q]; t[p]=x; return p;}
	int mid=(x+y)/2;
	lc[p]=merge(lc[p],lc[q],x,mid);
	rc[p]=merge(rc[p],rc[q],mid+1,y);
	pushup(p); return p;
}
void Redfs(int u) {
	for(int i=head[u]; i; i=nxt[i]) {
		int v=ver[i];
		if(deep[v]>deep[u]) {
			Redfs(v);
			rt[u]=merge(rt[u],rt[v],1,R);
		}
	}
	if(d[rt[u]]) ans[u]=t[rt[u]];
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1,x,y,z; i<n; i++) {
		scanf("%d%d",&x,&y);
		addedge(x,y); addedge(y,x);
	}
	deep[1]=1; dfs1(1); dfs2(1,1);
	for(int i=1; i<=m; i++) {
		scanf("%d%d%d",&qx[i],&qy[i],&qz[i]);
		R=max(R,qz[i]);
	}
	for(int i=1; i<=m; i++) {
		int s=lca(qx[i],qy[i]);
		rt[qx[i]]=modify(rt[qx[i]],1,R,qz[i],1);
		rt[qy[i]]=modify(rt[qy[i]],1,R,qz[i],1);
		rt[s]=modify(rt[s],1,R,qz[i],-1);
		if(fa[s]) rt[fa[s]]=modify(rt[fa[s]],1,R,qz[i],-1);
	}
	Redfs(1);
	for(int i=1; i<=n; i++) printf("%d\n",ans[i]);
	return 0;
}
2022/8/14 20:59
加载中...