某一天马学长给我看了一个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;
}