LG4556 [Vani有约会]雨天的尾巴 动态开点线段树+线段树合并

问题描述

LG4556

---

题解

对于每一个结点，建立一棵动态开点线段树。

然后自低向上合并线段树。

同时维护整个值域的最大值和最大值位置。

---

(mathrm{Code})

#include<bits/stdc++.h>
using namespace std;

template <typename Tp>
void read(Tp &x){
	x=0;char ch=1;int fh;
	while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
	if(ch=='-') ch=getchar(),fh=-1;
	else fh=1;
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	x*=fh;
}

const int maxn=1000007;
const int maxm=2000007;

int n,m;
int Head[maxn],Next[maxm],to[maxm],tot;

int size[maxn],fa[maxn],son[maxn];
int dep[maxn],top[maxn],du[maxn];

void add(int x,int y){
	to[++tot]=y,Next[tot]=Head[x],Head[x]=tot;
}

void dfs1(int x,int f,int dp){
	size[x]=1,fa[x]=f,dep[x]=dp;
	int mx=-1;
	for(int i=Head[x];i;i=Next[i]){
		int y=to[i];
		if(y==f) continue;
		dfs1(y,x,dp+1);size[x]+=size[y];
		if(size[y]>mx) mx=size[y],son[x]=y;
		++du[x];
	}
}

void dfs2(int x,int tp){
	top[x]=tp;
	if(!son[x]) return;
	dfs2(son[x],tp);
	for(int i=Head[x];i;i=Next[i]){
		int y=to[i];
		if(y==fa[x]||y==son[x]) continue;
		dfs2(y,y);
	}
}

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 L[maxn*22],R[maxn*22];
int rt[maxn],val[maxn*22],pos[maxn*22];
int cnt;

void pushup(int x){
	val[x]=max(val[L[x]],val[R[x]]);
	if(val[x]<=0) return;
	if(val[x]==val[L[x]]) pos[x]=pos[L[x]];
	else pos[x]=pos[R[x]];
}

int insert(int x,int l,int r,int p,int v){
	if(!x) x=++cnt;
	if(l==r){
		val[x]+=v,pos[x]=l;
		return x;
	}
	int mid=(l+r)>>1;
	if(p<=mid) L[x]=insert(L[x],l,mid,p,v);
	else R[x]=insert(R[x],mid+1,r,p,v);
	pushup(x);
	return x;
}

int ans[maxn];

int merge(int p,int q,int l,int r){
	if(!p||!q) return p+q;
	if(l==r){
		val[q]+=val[p],pos[q]=l;
		return q;
	}
	int mid=(l+r)>>1;
	L[q]=merge(L[p],L[q],l,mid);
	R[q]=merge(R[p],R[q],mid+1,r);
	pushup(q);
	return q;
}

int main(){
	read(n);read(m);
	for(int i=1,x,y;i<n;i++){
		read(x);read(y);
		add(x,y);add(y,x);
	}
	dfs1(1,0,1);dfs2(1,1);
	for(int i=1;i<=n;i++) rt[i]=++cnt;
	for(int i=1,x,y,z;i<=m;i++){
		read(x);read(y);read(z);
		int LCA=lca(x,y);
		insert(rt[x],1,100000,z,1);
		insert(rt[y],1,100000,z,1);
		insert(rt[LCA],1,100000,z,-1);
		insert(rt[fa[LCA]],1,100000,z,-1);
	}
	queue<int>q;
	for(int i=1;i<=n;i++){
		if(!du[i]) q.push(i);
	}
	while(!q.empty()){
		int x=q.front();q.pop();
		ans[x]=pos[rt[x]];
		merge(rt[x],rt[fa[x]],1,100000);
		--du[fa[x]];
		if(!du[fa[x]]) q.push(fa[x]);
	}
	for(int i=1;i<=n;i++){
		printf("%d
",ans[i]);
	}
	return 0;
}