P4556 【模板】线段树合并

题目描述

首先村落里的一共有 \(n\) 座房屋，并形成一个树状结构。然后救济粮分 \(m\) 次发放，每次选择两个房屋 \((x,~y)\)，然后对于 \(x\) 到 \(y\) 的路径上(含 \(x\) 和 \(y\))每座房子里发放一袋 \(z\) 类型的救济粮。

然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。

输入格式

输入的第一行是两个用空格隔开的正整数，分别代表房屋的个数 \(n\) 和救济粮发放的次数 \(m\)。

第 \(2\) 到 第 \(n\) 行，每行有两个用空格隔开的整数 \(a,~b\)，代表存在一条连接房屋 \(a\) 和 \(b\) 的边。

第 \((n + 1)\) 到第 \((n + m)\) 行，每行有三个用空格隔开的整数 \(x,~y,~z\)，代表一次救济粮的发放是从 \(x\) 到 \(y\) 路径上的每栋房子发放了一袋 \(z\) 类型的救济粮。

输出格式

输出 \(n\) 行，每行一个整数，第 \(i\) 行的整数代表 \(i\) 号房屋存放最多的救济粮的种类，如果有多种救济粮都是存放最多的，输出种类编号最小的一种。

如果某座房屋没有救济粮，则输出 \(0\)。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<ctime>
using namespace std;
const int N=1e5+5;
inline int read(){
	int x=0;char c=getchar();
	while(c<‘0‘||c>‘9‘) c=getchar();
    while(c>=‘0‘&&c<=‘9‘) x=(x<<3)+(x<<1)+c-48,c=getchar();
    return x;
}
int nxt[N<<1],head[N],go[N<<1],tot,Max;
inline void add(int u,int v){
	nxt[++tot]=head[u],head[u]=tot,go[tot]=v;
	nxt[++tot]=head[v],head[v]=tot,go[tot]=u;
}
int n,m,Dep[N],f[N][21];
void deal(int u,int father){
	Dep[u]=Dep[father]+1;
	for(int i=0;i<=19;i++)f[u][i+1]=f[f[u][i]][i];
	for(int e=head[u];e;e=nxt[e]){
		int v=go[e];
		if(v==father)continue;
		f[v][0]=u;
		deal(v,u);
	}
}
int LCA(int x,int y){
	if(Dep[x]<Dep[y])swap(x,y);
	for(int i=20;i>=0;i--)if(Dep[f[x][i]]>=Dep[y])x=f[x][i];
	if(x==y)return x;
	for(int i=20;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
	return f[x][0];
}
#define mid ((l+r)>>1)
struct Seg{
	int val,id,ls,rs;
	#define ls(p) tree[p].ls
	#define rs(p) tree[p].rs
	#define id(p) tree[p].id
	#define val(x) tree[x].val 
}tree[N<<10];
int root[N],num;
inline void pushup(int a) {
    if(val(ls(a))<val(rs(a)))val(a)=val(rs(a)),id(a)=id(rs(a));
    else val(a)=val(ls(a)),id(a)=id(ls(a));
}
void update(int &p,int l,int r,int pos,int d){
	if(!p)p=++num;
	if(l==r){ val(p)+=d,id(p)=l; return ; }
	if(pos<=mid)update(ls(p),l,mid,pos,d);
	else update(rs(p),mid+1,r,pos,d);
	pushup(p);
}
int merge(int l,int r,int u,int v){
	if(!u||!v) return u|v;;
	if(l==r){ val(u)+=val(v),id(u)=l; return u; }
	ls(u)=merge(l,mid,ls(u),ls(v));
	rs(u)=merge(mid+1,r,rs(u),rs(v));
	pushup(u);
	return u;
}
int ans[N];
void dfs(int u){
	for(int i=head[u];i;i=nxt[i]){
		int v=go[i];
		if(Dep[v]>Dep[u])dfs(v),root[u]=merge(1,Max,root[u],root[v]);
	}
	if(val(root[u]))ans[u]=id(root[u]);
}
int tx[N],ty[N],tz[N];
signed main(){
	n=read(),m=read();
	for(int i=1;i<n;i++)add(read(),read());
	deal(1,1);
	for(int i=1;i<=m;i++)tx[i]=read(),ty[i]=read(),tz[i]=read(),Max=max(tz[i],Max);
	for(int i=1,x,y,z;i<=m;i++){
		x=tx[i],y=ty[i],z=tz[i];
		int p=LCA(x,y);
		update(root[x],1,Max,z,1);
		update(root[y],1,Max,z,1);
		update(root[p],1,Max,z,-1);
		if(p!=1)update(root[f[p][0]],1,Max,z,-1);
	}
	dfs(1);
	for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
}

P4556 【模板】线段树合并

原文：https://www.cnblogs.com/naruto-mzx/p/13029005.html