某一天马学长给我看了一个lca的题目，然而确实是lca+树上差分，但是仅仅有lca和树上差分解决不了，然后我就去面向题解编程了。
可是这个线段树合并是个什么东东。。。
然而今天看书，突然看到了这个线段树合并。
就写一下了。
%mmh。

P4556 [Vani有约会]雨天的尾巴：
题目背景
深绘里一直很讨厌雨天。
灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。
虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被弄得一片狼藉。
无奈的深绘里和村民们只好等待救济粮来维生。
不过救济粮的发放方式很特别。

题目描述
首先村落里的一共有n座房屋，并形成一个树状结构。然后救济粮分m次发放，每次选择两个房屋(x,y)，然后对于x到y的路径上（含x和y)每座房子里发放一袋z类型的救济粮。
然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。

输入格式
第一行两个正整数n,m，含义如题目所示。
接下来n-1行，每行两个数(a,b)，表示(a,b)间有一条边。
再接下来m行，每行三个数(x,y,z)，含义如题目所示。

输出格式
n行，第i行一个整数，表示第i座房屋里存放的最多的是哪种救济粮，如果有多种救济粮存放次数一样，输出编号最小的。
如果某座房屋里没有救济粮，则对应一行输出0。

输入输出样例
输入 #1 复制
5 3
1 2
3 1
3 4
5 3
2 3 3
1 5 2
3 3 3
输出 #1 复制
2
3
3
0
2
说明/提示
对于20%的数据，1 <= n, m <= 100
对于50%的数据，1 <= n, m <= 2000
对于100%的数据，1 <= n, m <= 100000, 1 <= a, b, x, y <= n, 1 <= z <= 100000
Vani

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int maxn=100100;
struct node
{int lc,rc;int maxx,pos;
}t[maxn*20*4];int f[maxn][20],root[maxn],d[maxn],ans[maxn];
int head[maxn],ver[maxn*2],nt[maxn*2];
int xx[maxn],yy[maxn],zz[maxn],b[maxn];
int tot=1,n,m,tt,cnt=0,pm;void add(int x,int y)
{ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}void bfs(void)
{queue<int>q;q.push(1);d[1]=1;while(q.size()){int x=q.front();q.pop();for(int i=head[x];i;i=nt[i]){int y=ver[i];if(d[y]) continue;d[y]=d[x]+1;q.push(y);f[y][0]=x;for(int j=1;j<=tt;j++)f[y][j]=f[f[y][j-1]][j-1];}}
}int lca(int x,int y)
{if(d[x]>d[y]) swap(x,y);for(int i=tt;i>=0;i--)if(d[f[y][i]]>=d[x]) y=f[y][i];if(x==y) return x;for(int i=tt;i>=0;i--)if(f[y][i]!=f[x][i]) x=f[x][i],y=f[y][i];return f[x][0];
}int build(void)
{++cnt;t[cnt].lc=t[cnt].rc=t[cnt].maxx=t[cnt].pos=0;return cnt;
}void pushup(int p)
{t[p].maxx=max(t[t[p].lc].maxx,t[t[p].rc].maxx);t[p].pos=t[t[p].lc].maxx>=t[t[p].rc].maxx?t[t[p].lc].pos:t[t[p].rc].pos;
}void _insert(int p,int l,int r,int pos,int val)
{if(l==r){t[p].maxx+=val;t[p].pos=t[p].maxx>0?l:0;return ;}int mid=(l+r)>>1;if(pos<=mid){if(!t[p].lc) t[p].lc=build();_insert(t[p].lc,l,mid,pos,val);}else{if(!t[p].rc) t[p].rc=build();_insert(t[p].rc,mid+1,r,pos,val);}pushup(p);
}int _merge(int p,int q,int l,int r)
{if(!p) return q;if(!q) return p;if(l==r){t[p].maxx+=t[q].maxx;t[p].pos=t[p].maxx>0?l:0;return p;}int mid=(l+r)>>1;t[p].lc=_merge(t[p].lc,t[q].lc,l,mid);t[p].rc=_merge(t[p].rc,t[q].rc,mid+1,r);pushup(p);return p;
}void dfs(int x,int fa)
{for(int i=head[x];i;i=nt[i]){int y=ver[i];if(y==fa) continue;dfs(y,x);root[x]=_merge(root[x],root[y],1,pm);}ans[x]=t[root[x]].pos;
}int main(void)
{scanf("%d%d",&n,&m);tt=log(n)/log(2)+1;int x,y;for(int i=1;i<n;i++){scanf("%d%d",&x,&y);add(x,y),add(y,x);}for(int i=1;i<=m;i++)scanf("%d%d%d",&xx[i],&yy[i],&zz[i]),b[i]=zz[i];bfs();sort(b+1,b+m+1);pm=unique(b+1,b+m+1)-(b+1);for(int i=1;i<=n;i++) root[i]=build();for(int i=1;i<=m;i++)zz[i]=lower_bound(b+1,b+pm+1,zz[i])-b;for(int i=1;i<=m;i++){int fa=lca(xx[i],yy[i]);_insert(root[xx[i]],1,pm,zz[i],1);_insert(root[yy[i]],1,pm,zz[i],1);_insert(root[fa],1,pm,zz[i],-1);if(f[fa][0]) _insert(root[f[fa][0]],1,pm,zz[i],-1);}dfs(1,0);for(int i=1;i<=n;i++)printf("%d\n",b[ans[i]]);return 0;
}