线段树合并求助,10 分其余全 WA
查看原帖
线段树合并求助,10 分其余全 WA
629192
lisida0820楼主2023/1/13 20:52
#include <bits/stdc++.h>
namespace IO{
	#define LL long long
	inline LL read(){
		LL x=0,f=1;char c=getchar();
		for (;!isdigit(c);c=getchar())if (c=='-')f=-1;
		for (;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
		return x*f;
	}
	inline void write(LL x,char c='\n'){
		if (x){
			if (x<0)x=-x,putchar('-');
			char a[30];short l;
			for (l=0;x;x/=10)a[l++]=x%10^48;
			for (l--;l>=0;l--)putchar(a[l]);
		}else putchar('0');putchar(c);
	}
}using namespace IO;
using namespace std;

const int N = 1e5+10;
const int M = 1e7+10;
const int L = 100000;
struct edge{int to,nxt;}e[N<<1];
struct Sgt{int l,r,val;}tree[M];
int head[N],tot,f[N][30],dep[N],ans[N],root[N],n,m,cnt;
inline void add(int x,int y){e[++tot]={y,head[x]};head[x]=tot;}
void dfs(int x,int fa){
	f[x][0]=fa,dep[x]=dep[fa]+1;
	for (int i=1;i<=20;i++)
		f[x][i]=f[f[x][i-1]][i-1];
	for (int i=head[x];i;i=e[i].nxt)
		if (e[i].to!=fa)
			dfs(e[i].to,x);
}
inline int getlca(int x,int y){
	if (dep[x]>dep[y])swap(x,y);
	for (int i=20;i>=0;i--)
		if (dep[f[y][i]]>=dep[x])
			y=f[y][i];
	if (x==y)return x;
	for (int i=20;i>=0;i--)
		if (f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
int update(int pre,int l,int r,int x,int val){
	int now=++cnt,mid=(l+r)>>1;
	tree[now].l=tree[pre].l;
	tree[now].r=tree[pre].r;
	if (l==r){
		tree[now].val=tree[pre].val+val;
		return now;
	}
	if (x<=mid)tree[now].l=update(tree[pre].l,l,mid,x,val);
	else tree[now].r=update(tree[now].r,mid+1,r,x,val);
	tree[now].val=max(tree[tree[now].l].val,tree[tree[now].r].val);
	return now;
}
int merge(int x,int y){
	if (!x||!y)return x+y;
	tree[x].l=merge(tree[x].l,tree[y].l);
	tree[x].r=merge(tree[x].r,tree[y].r);
	if (!tree[x].l&&!tree[y].l){
		tree[x].val+=tree[y].val;
		return x;
	}
	tree[x].val=max(tree[tree[x].l].val,tree[tree[x].r].val);
	return x;
}
int query(int now,int l,int r){
	if (l==r)return l;
	int mid=(l+r)>>1;
	if (tree[tree[now].l].val>=tree[tree[now].r].val)
		return query(tree[now].l,l,mid);
	else
		return query(tree[now].r,mid+1,r);
}
void solve(int x,int fa){
	for (int i=head[x];i;i=e[i].nxt)
		if (e[i].to!=fa)
			solve(e[i].to,x),root[x]=merge(root[x],root[e[i].to]);
	if (!tree[root[x]].val)ans[x]=0;
	else ans[x]=query(root[x],1,L);
}
int main(){
	n=read(),m=read();
	for (int i=1,x,y;i<n;i++)x=read(),y=read(),add(x,y),add(y,x);
	dfs(1,0);
	for (int i=1;i<=m;i++){
		int x=read(),y=read(),z=read(),lca=getlca(x,y);
		root[x]=update(root[x],1,L,z,1);
		root[y]=update(root[y],1,L,z,1);
		root[lca]=update(root[lca],1,L,z,-1);
		root[f[lca][0]]=update(root[f[lca][0]],1,L,z,-1);
	}
	solve(1,0);
	for (int i=1;i<=n;i++)write(ans[i]);
	return 0;
}
2023/1/13 20:52
加载中...