2019.01.19 bzoj5457: 城市（线段树合并）

传送门

线段树合并菜题。

题意简述：给一棵树，每个节点有bib_ibi个aia_iai民族的人，问对于每棵子树，子树中哪个民族的人最多，有多少人。

思路：

直接上线段树合并，边合并边维护答案即可。

为了代码方便可以用pairpairpair来维护答案。

代码：

#include<bits/stdc++.h>
#define ri register int
#define lc (son[p][0])
#define rc (son[p][1])
#define fi first
#define se second
using namespace std;
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
const int N=4e5+5;
typedef pair<int,int> pii;
vector<int>e[N];
int n,m,tot=0,son[N*30][2],rt[N];
pii mx[N*30],ans[N];
inline void build(int&p,int l,int r,int k,int v){
	mx[p=++tot]=pii(v,-k),lc=rc=0;
	if(l==r)return;
	int mid=l+r>>1;
	k<=mid?build(lc,l,mid,k,v):build(rc,mid+1,r,k,v);
}
inline int merge(int x,int y,int l,int r){
	if(!x||!y)return x^y;
	if(mx[x].se^mx[y].se)mx[x]=max(mx[x],mx[y]);
	else mx[x]=pii(mx[x].fi+mx[y].fi,mx[x].se);
	if(l==r)return x;
	int mid=l+r>>1;
	son[x][0]=merge(son[x][0],son[y][0],l,mid);
	son[x][1]=merge(son[x][1],son[y][1],mid+1,r);
	return mx[x]=max(mx[son[x][0]],mx[son[x][1]]),x;
}
void dfs(int p,int fa){
	for(ri i=0,v;i<e[p].size();++i)if((v=e[p][i])^fa)dfs(v,p),rt[p]=merge(rt[p],rt[v],1,m);
	ans[p]=mx[rt[p]];
}
int main(){
	n=read(),m=read();
	for(ri i=1,u,v;i<n;++i)u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
	for(ri i=1,a,b;i<=n;++i)a=read(),b=read(),build(rt[i],1,m,a,b);
	dfs(1,0);
	for(ri i=1;i<=n;++i)cout<<-ans[i].se<<' '<<ans[i].fi<<'\n';
	return 0;
}

巴特西

2019.01.19 bzoj5457: 城市（线段树合并）

最新文章

热门文章