洛谷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\)。

样例 #1

样例输入 #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\%\) 的数据，保证 \(n, m \leq 100\)。
• 对于 \(50\%\) 的数据，保证 \(n, m \leq 2 \times 10^3\)。
• 对于 \(100\%\) 测试数据，保证 \(1 \leq n, m \leq 10^5\)，\(1 \leq a,b,x,y \leq n\)，\(1 \leq z \leq 10^5\)。

又是水题解的一题今天不写水题解，来把高端局，线段树合并，启动！！

正片开始

1.信息储存

由于需要维护的信息比较多，所以选择结构体更加直观。

code：

struct tree
{
    int l,r,sum,col;//左儿子，右儿子，权值最大值，救济粮类型
}tr[N*8];

2.向上更新

不会还有人会忘记向上更新8和一般线段树一样，也需要向上更新。

code：

void up(int rt)
{
    int l=tr[rt].l,r=tr[rt].r;
    if(tr[l].sum>=tr[r].sum)//左儿子更优
    {
        tr[rt].sum=tr[l].sum;
        tr[rt].col=tr[l].col;
    }
    else//右儿子更优
    {
        tr[rt].sum=tr[r].sum;
        tr[rt].col=tr[r].col;
    }
}

3.合并部分

大体分为两种情况：

1. 左儿子或右儿子为空。
2. 合并到叶子节点。

code：

int merge(int a,int b,int l,int r)//b和到a
{
    if(!a||!b) return a+b;//有子树为空
    if(l==r) {tr[a].sum+=tr[b].sum;return a;}//更新到子节点
    int mid=(l+r)>>1;//以下递归处理
    tr[a].l=merge(tr[a].l,tr[b].l,l,mid);
    tr[a].r=merge(tr[a].r,tr[b].r,mid+1,r);
    up(a);
    return a;
}

4.更新处理

利用树上差分将区间操作改为单点操作。

code：

void update(int &p,int l,int r,int t,int k)
{
    if(!p){p=++idx;}
    if(l==r){tr[p].sum+=k;tr[p].col=t;return;}
    int mid=(l+r)>>1;
    if(t<=mid) update(tr[p].l,l,mid,t,k);
    else update(tr[p].r,mid+1,r,t,k);
    up(p);
}

5.处理答案

搜一遍即可。

void dfs2(int u,int fa)
{
    for(auto v:g[u])
    {
        if(v==fa)continue;
        dfs2(v,u);
        root[u]=merge(root[u],root[v],1,100000);//将子树合并到根节点
    }
    if(tr[root[u]].sum==0) ans[u]=0;
    else ans[u]=tr[root[u]].col;
}

5.LCA处理

由于用到树上差分，所以需要维护两点的LCA信息。

code：

void dfs1(int u,int fa)
{
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(int i=1;i<21;i++) f[u][i]=f[f[u][i-1]][i-1];
    for(auto v:g[u])
    {
        if(v==fa){ continue;}
        dfs1(v,u);
    }
}//处理倍增信息。
int lca(int a,int b)
{
    if(dep[a]<dep[b]) swap(a,b);
    for(int i=20;i>=0;i--){if(dep[f[a][i]]>=dep[b])a=f[a][i];}
    if(a==b) return a;
    for(int i=20;i>=0;i--){if(f[a][i]!=f[b][i]){a=f[a][i],b=f[b][i];}}
    return f[a][0];
}

完整代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int n,m,u,v,w,a[N],root[N],idx,ans[N];
int dep[N],f[N][32];
vector<int>g[N];
struct tree
{
    int l,r,sum,col;//左儿子，右儿子，权值最大值，救济粮类型
}tr[N*8];
void dfs1(int u,int fa)
{
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(int i=1;i<21;i++) f[u][i]=f[f[u][i-1]][i-1];
    for(auto v:g[u])
    {
        if(v==fa){ continue;}
        dfs1(v,u);
    }
}
int lca(int a,int b)
{
    if(dep[a]<dep[b]) swap(a,b);
    for(int i=20;i>=0;i--){if(dep[f[a][i]]>=dep[b])a=f[a][i];}
    if(a==b) return a;
    for(int i=20;i>=0;i--){if(f[a][i]!=f[b][i]){a=f[a][i],b=f[b][i];}}
    return f[a][0];
}
void up(int rt)
{
    int l=tr[rt].l,r=tr[rt].r;
    if(tr[l].sum>=tr[r].sum)
    {
        tr[rt].sum=tr[l].sum;
        tr[rt].col=tr[l].col;
    }
    else
    {
        tr[rt].sum=tr[r].sum;
        tr[rt].col=tr[r].col;
    }
}
void update(int &p,int l,int r,int t,int k)
{
    if(!p){p=++idx;}
    if(l==r){tr[p].sum+=k;tr[p].col=t;return;}
    int mid=(l+r)>>1;
    if(t<=mid) update(tr[p].l,l,mid,t,k);
    else update(tr[p].r,mid+1,r,t,k);
    up(p);
}
int merge(int a,int b,int l,int r)//b和到a
{
    if(!a||!b) return a+b;
    if(l==r) {tr[a].sum+=tr[b].sum;return a;}
    int mid=(l+r)>>1;
    tr[a].l=merge(tr[a].l,tr[b].l,l,mid);
    tr[a].r=merge(tr[a].r,tr[b].r,mid+1,r);
    up(a);
    return a;
}
void dfs2(int u,int fa)
{
    for(auto v:g[u])
    {
        if(v==fa)continue;
        dfs2(v,u);
        root[u]=merge(root[u],root[v],1,100000);//将子树合并到根节点
    }
    if(tr[root[u]].sum==0) ans[u]=0;
    else ans[u]=tr[root[u]].col;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<n;i++){cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}
    dfs1(1,0);
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        update(root[u],1,100000,w,1);
        update(root[v],1,100000,w,1);
        int LCA=lca(u,v);
        update(root[LCA],1,100000,w,-1);
        update(root[f[LCA][0]],1,100000,w,-1);
    }
    dfs2(1,0);
    for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
    return 0;
}

完结收工！！！！！

个人主页

看完点赞，养成习惯

\(\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\)