[BZOJ3307] 雨天的尾巴（树上差分+线段树合并）

题面

给出一棵N个点的树，M次操作在链上加上某一种类别的物品，完成所有操作后，要求询问每个点上最多物品的类型。

N, M≤100000

分析

考虑树上差分。对于每条链(x,y),我们在x,y打一个+标记，lca(x,y)和lca(x,y)的父亲打一个-标记。然后在每个节点建立一棵权值线段树，下标v维护物品v的个数。如果有物品v，就把下标为v的位置+1，如果有-标记，就-1.线段树push_up的时候可以计算出最多物品的类型

然后从下往上线段树合并，合并到某个节点的时候就更新该节点的答案。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxn 100000

#define maxlogn 60

using namespace std;

int n,m;

struct edge{

	int from;

	int to;

	int next;

}E[maxn*2+5];

int sz=1;

int head[maxn+5];

void add_edge(int u,int v){

	sz++;

	E[sz].from=u;

	E[sz].to=v;

	E[sz].next=head[u];

	head[u]=sz;

}

int deep[maxn+5];

int anc[maxn+5][maxlogn+5];

void dfs1(int x,int fa){

	deep[x]=deep[fa]+1;

	anc[x][0]=fa;

	for(int i=1;i<=maxlogn;i++) anc[x][i]=anc[anc[x][i-1]][i-1];

	for(int i=head[x];i;i=E[i].next){

		int y=E[i].to;

		if(y!=fa){

			dfs1(y,x);

		}

	}

}

int lca(int x,int y){

	if(deep[x]<deep[y]) swap(x,y);

	for(int i=maxlogn;i>=0;i--){

		if(deep[anc[x][i]]>=deep[y]){

			x=anc[x][i];

		}

	}

	if(x==y) return x;

	for(int i=maxlogn;i>=0;i--){

		if(anc[x][i]!=anc[y][i]){

			x=anc[x][i];

			y=anc[y][i];

		}

	}

	return anc[x][0];

}

struct segment_tree{

#define lson(x) (tree[x].ls)

#define rson(x) (tree[x].rs)

	struct node{

		int ls;

		int rs;

		int cnt;

		int id;

	}tree[maxn*maxlogn+5];

	int ptr;

	void push_up(int x){

		if(tree[lson(x)].cnt>tree[rson(x)].cnt){

			tree[x].cnt=tree[lson(x)].cnt;

			tree[x].id=tree[lson(x)].id;

		}else if(tree[lson(x)].cnt==tree[rson(x)].cnt){

			tree[x].cnt=tree[lson(x)].cnt;

			tree[x].id=min(tree[lson(x)].id,tree[rson(x)].id);

		}else{

			tree[x].cnt=tree[rson(x)].cnt;

			tree[x].id=tree[rson(x)].id;

		}

	}

	void update(int &x,int upos,int uval,int l,int r){

		if(!x) x=++ptr;

		if(l==r){

			tree[x].cnt+=uval;

			tree[x].id=l;

			return;

		}

		int mid=(l+r)>>1;

		if(upos<=mid) update(tree[x].ls,upos,uval,l,mid);

		else update(tree[x].rs,upos,uval,mid+1,r);

		push_up(x);

	}

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

		if(!x||!y) return x+y;

		if(l==r){

			tree[x].cnt+=tree[y].cnt;

			tree[x].id=l;

			return x;

		}

		int mid=(l+r)>>1;

		tree[x].ls=merge(tree[x].ls,tree[y].ls,l,mid);

		tree[x].rs=merge(tree[x].rs,tree[y].rs,mid+1,r);

		push_up(x);

		return x;

	}

}T;

int root[maxn+5];

int ans[maxn+5];

int maxz;

struct query{

	int x;

	int y;

	int z;

}q[maxn+5];

void dfs2(int x,int fa){

	for(int i=head[x];i;i=E[i].next){

		int y=E[i].to;

		if(y!=fa){

			dfs2(y,x);

			root[x]=T.merge(root[x],root[y],1,maxz);

		}

	}

	if(T.tree[root[x]].cnt) ans[x]=T.tree[root[x]].id;

	else ans[x]=0;

}

int main(){

	int u,v;

	scanf("%d %d",&n,&m);

	for(int i=1;i<n;i++){

		scanf("%d %d",&u,&v);

		add_edge(u,v);

		add_edge(v,u);

	}

	dfs1(1,0);

	maxz=0;

	for(int i=1;i<=m;i++){

		scanf("%d %d %d",&q[i].x,&q[i].y,&q[i].z);

		maxz=max(q[i].z,maxz);

	}

	for(int i=1;i<=m;i++){

		int x=q[i].x,y=q[i].y,z=q[i].z,lc=lca(x,y);

		T.update(root[x],z,1,1,maxz);

		T.update(root[y],z,1,1,maxz);

		T.update(root[lc],z,-1,1,maxz);

		T.update(root[anc[lc][0]],z,-1,1,maxz);

	}

	dfs2(1,0);

	for(int i=1;i<=n;i++){

		printf("%d\n",ans[i]);

	}

}

巴特西

[BZOJ3307] 雨天的尾巴（树上差分+线段树合并）

[BZOJ3307] 雨天的尾巴（树上差分+线段树合并）

题面

分析

代码

最新文章

热门文章