线段树合并20pts求调
查看原帖
线段树合并20pts求调
684285
Makerlove楼主2024/9/9 17:48
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef pair<int,int> pi;
template<typename T>
inline void read(T &x){
	x=0;
	char ch=getchar();
	int f=1;
	while(!isdigit(ch)){
		if(ch=='-')
			f*=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=x*10+ch-48;
		ch=getchar();
	}
	x*=f;
}
template<typename T, typename... Args>
inline void read(T &first, Args& ... args){
	read(first);
	read(args...);
}
template<typename T>
inline void write(T arg){
	T x=arg;
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9){
		write(x/10);
	}
	putchar(x%10+'0');
}
template<typename T, typename ... Ts>
inline void write(T arg, Ts ... args){
	write(arg);
	if(sizeof...(args)!=0){
		putchar(' ');
		write(args ...);
	}
}
const int N=2e5+10;
int n,q,m;
struct edge{
	int v,nxt;
}e[N];
int hd[N],tt;
void init(){
	memset(hd,-1,sizeof(hd));
}
void add(int x,int y){
	e[++tt].v=y;
	e[tt].nxt=hd[x];
	hd[x]=tt;
}
int fa[N],son[N],dep[N],siz[N];
void dfs1(int u){
	siz[u]=1;
	for(int i=hd[u];~i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa[u])
			continue;
		fa[v]=u,dep[v]=dep[u]+1;
		dfs1(v);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])
			son[u]=v;
	}
}
int top[N];
void dfs2(int u,int t){
	top[u]=t;
	if(son[u])
		dfs2(son[u],t);
	for(int i=hd[u];~i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa[u]||v==son[u])
			continue;
		dfs2(v,v);
	}
}
int get_lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		x=fa[top[x]]; 
	}
	return dep[x]<dep[y]?x:y;
}
int rt[N],tot;
struct tree{
	int ls,rs;
	pi mx;
}tr[N<<5];
pi Max(pi A,pi B){
	if(A.first!=B.first)
		return A.first>B.first?A:B;
	return A.second<B.second?A:B;
}
void pushup(int p){
	tr[p].mx=Max(tr[tr[p].ls].mx,tr[tr[p].rs].mx);
}
void update(int &p,int l,int r,int x,int v){
	if(!p)
		p=++tot;
	if(l==r){
		tr[p].mx.first+=v;
		tr[p].mx.second=l;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
		update(tr[p].ls,l,mid,x,v);
	else
		update(tr[p].rs,mid+1,r,x,v);
	pushup(p);
}
int merge(int p1,int p2,int l,int r){
	if(!p1)
		return p2;
	if(!p2)
		return p1;
	if(l==r){
		tr[p1].mx.first+=tr[p2].mx.first;
		return p1;
	}
	int mid=(l+r)>>1;
	tr[p1].ls=merge(tr[p1].ls,tr[p2].ls,l,mid);
	tr[p1].rs=merge(tr[p1].rs,tr[p2].rs,mid+1,r);
	pushup(p1);
	return p1;
}
int ans[N];
void solve(int u){
	for(int i=hd[u];~i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa[u])
			continue;
		solve(v);
		merge(rt[u],rt[v],1,N-1);
	}
	ans[u]=tr[rt[u]].mx.second;
}
signed main(){
	init();
	read(n,q);
	for(int i=1,x,y;i<n;i++){
		read(x,y);
		add(x,y),add(y,x);
	}
	dfs1(1);
	dfs2(1,1);
	for(int i=1,x,y,z,lca;i<=q;i++){
		read(x,y,z);
		lca=get_lca(x,y);
		update(rt[x],1,N-1,z,1);
		update(rt[y],1,N-1,z,1);
		update(rt[lca],1,N-1,z,-1);
		update(rt[fa[lca]],1,N-1,z,-1);
	}
	solve(1);
	for(int i=1;i<=n;i++){
		write(ans[i]);
		putchar('\n');
	}
	return 0;
}
2024/9/9 17:48
加载中...