P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并

Liuboom · 2025-04-24 18:01:00 · 个人记录

P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并

题目背景

深绘里一直很讨厌雨天。

灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。

虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被弄得一片狼藉。

无奈的深绘里和村民们只好等待救济粮来维生。

不过救济粮的发放方式很特别。

题目描述

村落里一共有 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。

说明/提示

• 对于 100\% 测试数据，保证 1 \leq n, m \leq 10^5，1 \leq a,b,x,y \leq n，1 \leq z \leq 10^5。

Solution:

发现我线段树合并的板子题居然没写，顺手补一下。

首先我们看到题面不难想到树上差分一下，维护一个桶，表示当前的房屋下的救济粮的状态，我们需要维护两个值, num_x,type_x 分别表示当前节点下最多的救济粮的数量和其对应的编号。

那么我们显然是希望这个桶可以向上合并的，不然我们就不好差分了，但是直接扫描一遍的话时间复杂度又会令人难以接受，所以我们需要一种十分快速的合并方法。不难发现，我们需要差分的点的个数是 O(n) 级别的，所以救济粮的种类也是 O(n) 级别的。我们开一颗线段树维护 num,type 然后对于一个节点 x 他的线段树就由他的所有儿子 y 的线段树合并再加上挂在这个点上的差分得到。

那么我们如何实现快速的线段树合并呢？假设我们现在在合并两颗线段树 x,y ：如果在区间 [l,r] 在 x 上存在而在 y 上不存在，那么合并后的树 ans 的 [l,r] 区间直接指向 [l,r] ，如果两棵树都有这个区间，那么就向下递归，如果递归到了单点，直接相加然后 return.

不难发现这样做的时间复杂度是 O(logn\times K) 其中 K 表示 x,y 两个线段树上的重合部分，由于我们动态开点只会开出至多 n 个，所以重合部分并不会很多，并且 O(logn) 递归的时候有很多区间其实是重合的，也就是说前面的 O(logn) 是能被均摊到更小的。

再有就是其实我们只差分了四个点，所以需要 upd 的点也不是特别多，合并时大多数的点都是直接挂就好了，所以复杂度其实不会很卡。

感觉我的复杂度分析有点胡扯啊，如果以后想到更好的写法再补

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=6e6+5;
int n,cnt,df,node,m,R;
int head[N],dep[N],fa[N],son[N],len[N],top[N],dfn[N],root[N];
int xx[N],yy[N],zz[N],num[N],ty[N],ls[N],rs[N],ans[N];
struct Edge{
    int to,nxt;
}edge[N<<1];
void add(int x,int y)
{
    edge[++cnt]=(Edge){y,head[x]};head[x]=cnt;
}
void init()
{
    for(int i=1;i<=n+1;i++)
    {
        head[i]=-1;
    }
}
void dfs1(int x,int f)
{
    dep[x]=dep[f]+1;len[x]=1;fa[x]=f;
    int maxlen=0;
    for(int i=head[x];~i;i=edge[i].nxt)
    {
        int to=edge[i].to;
        if(to==f)continue;
        dfs1(to,x);
        len[x]+=len[to];
        if(len[to]>maxlen)
        {
            maxlen=len[to];
            son[x]=to;
        }
    }
}
void dfs2(int x,int tp)
{
    top[x]=tp;dfn[x]=++df;
    if(!son[x])return;
    dfs2(son[x],tp);
    for(int i=head[x];~i;i=edge[i].nxt)
    {
        int to=edge[i].to;
        if(to==fa[x]||to==son[x])continue;
        dfs2(to,to);
    }
}
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]];
    }
    if(dep[x]<dep[y])swap(x,y);
    return y;
}
void pushup(int x)
{
    if(num[ls[x]]>=num[rs[x]])
    {
        num[x]=num[ls[x]];
        ty[x]=ty[ls[x]];
    }
    else
    {
        num[x]=num[rs[x]];
        ty[x]=ty[rs[x]];
    }
    return ;
}
int upd(int x,int ll,int rr,int type,int val)
{
    if(!x)x=++node;
    if(ll==rr)
    {
        num[x]+=val;ty[x]=ll;
        return x;
    }
    int mid=ll+rr>>1;
    if(type<=mid)ls[x]=upd(ls[x],ll,mid,type,val);
    else rs[x]=upd(rs[x],mid+1,rr,type,val);
    pushup(x);
    return x;
}
int merge(int x,int y,int ll,int rr)
{
    if(!y)return x;
    if(!x)return y;
    if(ll==rr)
    {
        num[x]+=num[y];
        ty[x]=ll;
        return x;
    }
    int mid=ll+rr>>1;
    ls[x]=merge(ls[x],ls[y],ll,mid);
    rs[x]=merge(rs[x],rs[y],mid+1,rr);
    pushup(x);
    return x;
}
void ANS(int x)
{
    for(int i=head[x];~i;i=edge[i].nxt)
    {
        int to=edge[i].to;
        if(dep[to]<dep[x])continue;
        ANS(to);root[x]=merge(root[x],root[to],1,R);
    }
    if(num[root[x]])
    {
        ans[x]=ty[root[x]];
    }
}
int main()
{
    //freopen("p4556.in","r",stdin);
    //freopen("p4556.out","w",stdout);
    cin>>n>>m;
    init();
    for(int i=1,x,y;i<n;i++)
    {
        cin>>x>>y;
        add(x,y),add(y,x);

    }
    dfs1(1,0);
    dfs2(1,1);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&xx[i],&yy[i],&zz[i]);
        R=max(R,zz[i]);
    }
    for(int i=1;i<=m;i++)
    {
        int lca=Lca(xx[i],yy[i]);
        root[xx[i]]=upd(root[xx[i]],1,R,zz[i],1);
        root[yy[i]]=upd(root[yy[i]],1,R,zz[i],1);
        root[lca]=upd(root[lca],1,R,zz[i],-1);
        if(fa[lca])root[fa[lca]]=upd(root[fa[lca]],1,R,zz[i],-1);
    }
    ANS(1);
    for(int i=1;i<=n;i++)
    {
        printf("%d\n",ans[i]);
    }
    return 0;
}