P4556 [Vani有约会]雨天的尾巴（线段树合并）

传送门

一道线段树合并

首先不难看出树上差分

我们把每一次修改拆成四个，在\(u,v\)分别放上一个，在\(lca\)和\(fa[lca]\)各减去一个，那么只要统计一下子树里的总数即可

然而问题就在于怎么统计。直接暴力肯定是要咕咕的，那么线段树合并就派上用场了

总之就是每个点开一个动态开点线段树，然后一遍dfs，让它的所有儿子的线段树合并到它这里

我按以前的写法不知为什么写挂了……然后换抄了种写法还是挂……后来发现是写抄的时候没有注意合并的顺序……

//minamoto

#include<bits/stdc++.h>

#define IT vector<node>::iterator

#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)

#define go(u) for(register int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

using namespace std;

#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

char buf[1<<21],*p1=buf,*p2=buf;

int read(){

    int res,f=1;char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

char sr[1<<21],z[20];int C=-1,Z=0;

inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}

void print(int x){

    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;

    while(z[++Z]=x%10+48,x/=10);

    while(sr[++C]=z[Z],--Z);sr[++C]='\n';

}

const int N=1e5+5;

struct node{

	int c,cnt;

//	inline bool operator <(node b){return cnt==b.cnt?c>b.c:cnt<b.cnt;}

	friend bool operator <(node a,node b){return a.cnt==b.cnt?a.c>b.c:a.cnt<b.cnt;}

	inline node operator +(node b){return {c,cnt+b.cnt};}

};vector<node>v[N];

struct eg{int v,nx;}e[N<<1];int head[N],tot;

inline void add(int u,int v){e[++tot]={v,head[u]},head[u]=tot;}

int rt[N],fa[N],dfn[N],top[N],sz[N],son[N],dep[N],ans[N],n,m,u,vva,c;

void dfs1(int u){

	sz[u]=1,dep[u]=dep[fa[u]]+1;

	go(u)if(v!=fa[u]){

		fa[v]=u,dfs1(v),sz[u]+=sz[v];

		if(sz[v]>sz[son[u]])son[u]=v;

	}

}

void dfs2(int u,int t){

	top[u]=t;if(!son[u])return;dfs2(son[u],t);

	go(u)if(v!=fa[u]&&v!=son[u])dfs2(v,v);

}

inline int LCA(int u,int v){

	while(top[u]!=top[v]){

		if(dep[top[u]]<dep[top[v]])swap(u,v);

		u=fa[top[u]];

	}return dep[u]<dep[v]?u:v;

}

namespace LOLI{

	int L[N<<5],R[N<<5],tot;node v[N<<5];

	inline void init(){fp(i,1,n)rt[i]=++tot;}

	void ins(int p,int l,int r,node val){

		if(l==r)return (void)(v[p]=val+v[p]);int mid=(l+r)>>1;

		if(val.c<=mid)ins(L[p]=L[p]?L[p]:++tot,l,mid,val);

		else ins(R[p]=R[p]?R[p]:++tot,mid+1,r,val);v[p]=max(v[L[p]],v[R[p]]);

	}

	void merge(int x,int y,int l,int r){

//		printf("%d %d %d %d\n",x,y,l,r);

		if(l==r)return (void)(v[x]=v[x]+v[y]);int mid=(l+r)>>1;

		if(L[x]&&L[y])merge(L[x],L[y],l,mid);else if(L[y])L[x]=L[y];

		if(R[x]&&R[y])merge(R[x],R[y],mid+1,r);else if(R[y])R[x]=R[y];

		v[x]=max(v[L[x]],v[R[x]]);

	}

}

void dfs(int u){

//	printf("%d\n",u);

	go(u)if(v!=fa[u])dfs(v),LOLI::merge(rt[u],rt[v],1,1e5);

	for(IT it=v[u].begin();it!=v[u].end();++it)LOLI::ins(rt[u],1,1e5,*it);

	ans[u]=LOLI::v[rt[u]].c;

}

int main(){

//	freopen("testdata.in","r",stdin);

	n=read(),m=read(),LOLI::init();

	fp(i,1,n-1)u=read(),vva=read(),add(u,vva),add(vva,u);

	dfs1(1),dfs2(1,1);

	fp(i,1,m){

		u=read(),vva=read(),c=read();int lca=LCA(u,vva);

		v[u].push_back(node{c,1}),v[vva].push_back(node{c,1});

		v[lca].push_back(node{c,-1}),v[fa[lca]].push_back(node{c,-1});

	}dfs(1);fp(i,1,n)print(ans[i]);return Ot(),0;

}

巴特西

P4556 [Vani有约会]雨天的尾巴（线段树合并）

最新文章

热门文章