.png)
前言
线段树合并是一种可以在 O(n\log{n}) 的时间复杂度内对多颗线段树的信息进行合并处理的操作，一般情况下用于对权值线段树进行合并（根据其信息可合并的性质）。
前置知识
- 线段树
- 权值线段树并且会动态开点 （这里直接贴了 BFqwq 的洛谷日报，拜谢喵）
- 最近公共祖先 （会用一般操作求就行，用于树上差分，这里贴了我自己的题解，是树剖求法 OvO）
- 树上差分（点差分）
题目分析
在讲解线段树合并之前，我们先对这道题目做一些简单的思考，因为这个模板实际上并不完全板，想直接学习线段树合并的同学可以直接跳到文章后面部分的“算法解析”。
从简单考虑，只有一个房屋
说起来有点弱智，但是一道题的正解思路本身就是从一些不起眼的部分分或简单性质堆建起来的。
对权值开桶统计救济粮信息，最后 O(权值) 地遍历桶寻找出现次数最多的救济粮。
启示 1：需要有类似桶的思想统计信息。
每次分发到从x到y的路径
这下不能暴力统计了，我们需要一种方式把路径上分发的救济粮的操作转化为更快的点上操作，考虑树上差分，每次只修改 x、y 及其 LCA 和 LCA 的父节点。
启示 2：树上差分降低路径修改的时间复杂度。
有了差分肯定还要进行合并才能统计最终的答案，这时候又有问题，如果我们每次对桶进行暴力合并，时间复杂度又会爆炸，我们需要换一种方式，但要保证：
- 有桶的功能。
- 可以以更优的时间复杂度进行合并。
启示 3：考虑给每个房屋开一颗权值线段树然后线段树合并（虽然你还不会，但我马上教你 OvO）。
接下来正式进入算法讲解。
算法解析
由于权值线段树是在叶子节点上对权值开桶统计信息的，合并的过程实际上就是从两颗线段树的根节点 x，y 开始深搜，分三种情况：
- 若其中一个节点为空，则返回非空的节点作为合并后的节点。
- 若两个节点均不为空，先递归继续合并子树信息，合并完后返回 x 作为最终合并后的节点（y 也行，不过就是需要只保留一个节点）。
- 合并到了叶子节点，就把两个节点的信息加起来。
因为叶子节点的信息通过合并已经统计好了，那么其他的节点我们只需要 pushup() 上来即可。
根据上述说明，我们可以给出线段树合并操作的 merge() 函数：
代码实现
//xy是要合并的节点编号，lr是'值域'区间
int merge(int x,int y,int l,int r){//合并
if(!x||!y) return x+y;//其中一个是空树，返回另一个的编号
//l==r --> 是叶子节点，把y的值加给x，返回x节点编号
if(l==r){sum[x]+=sum[y];return x;}
int mid=(l+r)>>1;
//左右儿子递归合并
ls[x]=merge(ls[x],ls[y],l,mid);
rs[x]=merge(rs[x],rs[y],mid+1,r);
pushup(x);//更新节点信息
return x;
}
实际上这段代码就是线段树合并的核心代码了，我们接下来进行复杂度分析。
时间复杂度
容易发现，merge() 函数只有在两颗线段树的某一节点都不为空时才会进行调用，换句话说，其调用次数只与两颗线段树重叠存在的节点数量有关，我们动态开点的线段树的节点数量是 O(\log n) 级别的，故这里合并两颗线段树的时间复杂度就是 O(\log n) 级别的。合并完所有房屋，总时间复杂度就是 O(n \log n) 级别的。
空间复杂度
在本题中，我们一共进行 m 次操作，每次单点修改最多在一颗动态开点线段树上产生 \log n 个节点，同时一次操作要修改 4 个节点，故我们最多要存下 4 \times m \times \log{n} 个节点，级别在 O（m\log n）。
完整代码
由于本题除了线段树合并外，也伴有其他操作，所以笔者在代码中加了不少注释，如果影响观感请见谅
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,ans[N];
int dep[N],siz[N],son[N],fa[N],top[N];
struct node{
int next,to;
}e[N<<1];
int tot,head[N];
//--------权值线段树相关
int root[N],cnt;
//root存储每个房屋所对应线段树的根节点编号
int ls[N*50],rs[N*50],sum[N*50],z[N*50];
//空间大小:m*4*logn 原因:树上差分修改四次，动态开点至多logn个点，一共操作m次
void add(int x,int y){
e[++tot].to=y;
e[tot].next=head[x];
head[x]=tot;
}
//----------lca部分，用于树上差分，使用任意复杂度正确的lca求法皆可，这里是树剖
void dfs1(int x,int f){
siz[x]=1;
fa[x]=f;
dep[x]=dep[f]+1;
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(y!=f){
dfs1(y,x);
siz[x]+=siz[y];
if(siz[son[x]]<siz[y] || !son[x]){
son[x]=y;
}
}
}
}
void dfs2(int x,int t){
top[x]=t;
if(!son[x])return ;
dfs2(son[x],t);
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(y!=fa[x] && y!=son[x]){
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]];
}
return dep[x]<dep[y]?x:y;
}
//-----------------------权值线段树部分
void pushup(int i){//更新父亲节点
if(sum[ls[i]]>=sum[rs[i]]){
//从叶子节点开始想
//左儿子的sum>右儿子的sum
//也就是左儿子掌管的值的权值最大，是一整个值域区间出现次数最多的值
//就更新，按题意次数相等的话，输出更小的，所以判断带上相等
sum[i]=sum[ls[i]],z[i]=z[ls[i]];
}else{//同理
sum[i]=sum[rs[i]],z[i]=z[rs[i]];
}
}
//i是节点编号，lr是'值域'区间，p是救济粮种类，k是sum修改值
void change(int &i,int l,int r,int p,int k){
//如果该节点编号为0,就新建一个节点
if(!i) i=++cnt;
//l==r --> 是叶子节点，该节点只管一个值域即lr或者说p
if(l==r){sum[i]+=k; z[i]=p; return;}
int mid=(l+r)>>1;
if(p<=mid) change(ls[i],l,mid,p,k);
else change(rs[i],mid+1,r,p,k);
pushup(i);
}
//xy是要合并的节点编号，lr是'值域'区间
int merge(int x,int y,int l,int r){//合并
if(!x||!y) return x+y;//其中一个是空树，返回另一个的编号
//l==r --> 是叶子节点，把y的值加给x，返回x节点编号
if(l==r){sum[x]+=sum[y];return x;}
int mid=(l+r)>>1;
//左右儿子递归合并
ls[x]=merge(ls[x],ls[y],l,mid);
rs[x]=merge(rs[x],rs[y],mid+1,r);
pushup(x);//更新节点信息
return x;
}
//------------第三次dfs依次合并线段树信息
void dfs3(int x,int f){
for(int i=head[x];i;i=e[i].next){//遍历儿子合并
int y=e[i].to;
if(y==f) continue;
dfs3(y,x);
//递归到叶子节点的房屋对应的线段树，将其不断与父亲节点合并
//合并的过程中，就是不断求子树和的过程，此时父亲节点的线段树获取了应参与计算的救济粮
root[x]=merge(root[x],root[y],1,N);
}
//答案就是x对应线段树里出现次数最多的值
//不能直接赋值为z[root[x]]，因为为0时可能存在没有分到救济粮但是z数组却因为差分做法被赋值
//sum为真则取z[root[x]],为假则取0
ans[x]=sum[root[x]]?z[root[x]]:0;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
for(int i=1;i<=n-1;i++){
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=m;i++){//树上差分，给x,y两个点加1,lca和lca的父节点两个点减1，最后进行子树求和即可得到x到y的路径加一的结果
int x,y,z;
cin>>x>>y>>z;
change(root[x],1,N,z,1);
change(root[y],1,N,z,1);
int t=lca(x,y);
change(root[t],1,N,z,-1);
change(root[fa[t]],1,N,z,-1);
}
dfs3(1,0);
for(int i=1;i<=n;i++){
cout<<ans[i]<<endl;
}
return 0;
}
后记
在这里为大家推荐几道线段树合并的练手题：
- CF600E Lomsat gelral（这道才是真正裸的模板题）
- P3224 永无乡
- P1600 天天爱跑步
- P3521 ROT-Tree Rotations
同时，本题除了线段树合并的做法外，还有树剖做法，并不在本文讲解范畴，但如果你还没有了解过树剖，那就巧了，因为我写过 题解：P3384 【模板】重链剖分/树链剖分 感兴趣的同学可以从这篇题解中学习。