前言

因为一开始没有理解透彻线段树合并，一直错样例。。。
然后想着“反正调试也调不出什么”，然后盯着\(merge\)看了\(1.5h\)，对着各种标程找错。
最后放弃肉眼观察，抱着试试看的心态去调试。
结果发现是\(lca\)写错了。。。我带你们打。。。

题目

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

思路

线段树合并模板。
我们在树的每一个节点处开一棵动态开点的线段树，线段树的一个叶子结点\([x,x]\)表示这个（树的而不是线段树的）节点有多少个\(x\)型号的救济粮。维护区间\(max\)以及它的位置\(pos\)。
那么对于一个修改操作\(x,y,k\)，求出\(x,y\)的\(lca\)点\(z\)，然后差分思想，在\(x,y\)两个节点的线段树的\(k\)处\(+1\)，\(z\)和\(fa[z]\)两个节点的线段树的\(k\)处\(-1\)。
修改操作完成后，从下往上线段树合并。合并完\(x\)为根的子树时，就可以统计\(x\)的答案了。
时间复杂度\(O(n\log n)\)。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=100010,LG=18;
int n,m,tot,head[N],f[N][LG+1],dep[N],rt[N],U[N],V[N],Z[N],b[N],ans[N];

struct edge
{
    int next,to;
}e[N*2];

void add(int from,int to)
{
    e[++tot].to=to;
    e[tot].next=head[from];
    head[from]=tot;
}

void dfs1(int x,int fa)
{
    dep[x]=dep[fa]+1; f[x][0]=fa;
    for (int i=1;i<=LG;i++)
        f[x][i]=f[f[x][i-1]][i-1];
    for (int i=head[x];~i;i=e[i].next)
        if (e[i].to!=fa) dfs1(e[i].to,x);
}

int lca(int x,int y)
{
    if (dep[x]<dep[y]) swap(x,y);
    for (int i=LG;i>=0;i--)
        if (dep[f[x][i]]>=dep[y]) x=f[x][i];
    if (x==y) return x;
    for (int i=LG;i>=0;i--)
        if (f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}

struct Treenode
{
    int lc,rc,maxn,pos;
};

struct Tree
{
    Treenode tree[N*LG*3];
    int totel;
    
    void pushup(int x)
    {
        if (tree[tree[x].lc].maxn>=tree[tree[x].rc].maxn)
        {
            tree[x].maxn=tree[tree[x].lc].maxn;
            tree[x].pos=tree[tree[x].lc].pos;
        }
        else
        {
            tree[x].maxn=tree[tree[x].rc].maxn;
            tree[x].pos=tree[tree[x].rc].pos;
        }
    }
    
    void update(int &x,int l,int r,int k,int val)
    {
        if (!x) x=++totel;
        if (l==k && r==k)
        {
            tree[x].maxn+=val;
            tree[x].pos=k;
            return;
        }
        int mid=(l+r)>>1;
        if (k<=mid) update(tree[x].lc,l,mid,k,val);
            else update(tree[x].rc,mid+1,r,k,val);
        pushup(x);
    }
    
    void merge(int &x,int y,int l,int r)
    {
        if (!x || !y) x+=y;
        else if (l==r) tree[x].maxn+=tree[y].maxn;
        else
        {
            int mid=(l+r)>>1;
            merge(tree[x].lc,tree[y].lc,l,mid);
            merge(tree[x].rc,tree[y].rc,mid+1,r);
            pushup(x);
        }
    }
}tree;

void dfs2(int x)
{
    for (int i=head[x];~i;i=e[i].next)
        if (e[i].to!=f[x][0])
        {
            dfs2(e[i].to);
            tree.merge(rt[x],rt[e[i].to],1,tot);
        }
    if (tree.tree[rt[x]].maxn) ans[x]=tree.tree[rt[x]].pos;
}

int main()
{
    //freopen("data.in","r",stdin);
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for (int i=1,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y); add(y,x);
    }
    dfs1(1,0);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&U[i],&V[i],&Z[i]);
        b[i]=Z[i]; 
    }
    sort(b+1,b+1+m);
    tot=unique(b+1,b+1+m)-b-1;
    for (int i=1;i<=m;i++)
        Z[i]=lower_bound(b+1,b+1+tot,Z[i])-b;
    for (int i=1;i<=m;i++)
    {
        int LCA=lca(U[i],V[i]);
        tree.update(rt[U[i]],1,tot,Z[i],1); tree.update(rt[V[i]],1,tot,Z[i],1);
        tree.update(rt[LCA],1,tot,Z[i],-1);
        if (f[LCA][0]) tree.update(rt[f[LCA][0]],1,tot,Z[i],-1);
    }
    dfs2(1);
    for (int i=1;i<=n;i++)
        printf("%d\n",b[ans[i]]);
    return 0;
}

【洛谷P4556】雨天的尾巴 /【模板】线段树合并

原文：https://www.cnblogs.com/stoorz/p/12242685.html