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

· · 个人记录

深绘里一直很讨厌雨天。

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

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

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

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

首先村落里的一共有 n 座房屋，并形成一个树状结构。然后救济粮分 m 次发放，每次选择两个房屋 (x,y) ，然后对于 x 到 y 的路径上(含 x 和 y )每座房子里发放一袋 z 类型的救济粮。

然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。

数据范围

1≤n,m≤10^5 1 \leq a,b,x,y \leq n 1 \leq z \leq 10^5

链接

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

思路

线段树合并板子。

首先考虑只有一种类型的救济粮时可以直接树上差分。

而本题有多达 10^5 种救济粮。

所以可以考虑线段树合并。

当然树剖也可以搞，拆链后对每个链进行差分最后统计即可。

线段树合并复杂度 O(n\log n) ，树剖解法复杂度 O(n\log^2 n) 。

线段树合并注意当救济粮种类数量为 0 时记录的种类也要清零。

代码（线段树合并）

#include<bits/stdc++.h>
#define N 100010
#define Log 20
#define MAXN 100000

using namespace std;

inline int read() {
    int w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int head[N],tot=0;
struct graph{
    int v,next;
}edge[N<<1];
inline void add(int u,int v) {
    edge[++tot].v=v;
    edge[tot].next=head[u];
    head[u]=tot;
}

int root[N];
class SegmengTree{
  private:
    int numn[N*Log<<2],id[N*Log<<2],lson[N*Log<<2],rson[N*Log<<2],total=0;
    #define n(x) numn[x]
    #define id(x) id[x]
    #define ls(x) lson[x]
    #define rs(x) rson[x]
    #define mid (l+r>>1)
    inline void update(int p) {
        if(n(ls(p))>=n(rs(p))) n(p)=n(ls(p)),id(p)=id(ls(p));
        else n(p)=n(rs(p)),id(p)=id(rs(p));
    }
  public:
    void change(int &p,int l,int r,int x,int y) {
        if(!p) p=++total;
        if(l==r) {
            n(p)+=y;
            id(p)=l;
            if(!n(p)) id(p)=0;
            return ;
        }
        if(x<=mid) change(ls(p),l,mid,x,y);
        else change(rs(p),mid+1,r,x,y);
        update(p);
    }
    int merge(int p,int q,int l,int r) {
        if(!p||!q) return p+q;
        if(l==r) {
            n(p)=n(p)+n(q);
            id(p)=l;
            if(!n(p)) id(p)=0;
            return p;
        }
        ls(p)=merge(ls(p),ls(q),l,mid);
        rs(p)=merge(rs(p),rs(q),mid+1,r);
        update(p);
        return p;
    }
    inline int ask(int p) {return id(p);}
}SMT;

int depth[N],fa[N][Log],lg[N];
void dfs(int u) {
    for(int i=1;i<=lg[depth[u]];i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].v;
        if(v==fa[u][0]) continue;
        depth[v]=depth[u]+1;
        fa[v][0]=u;
        dfs(v);
    }
}
int LCA(int x,int y) {
    if(depth[x]<depth[y]) swap(x,y);
    while(depth[x]>depth[y]) x=fa[x][lg[depth[x]-depth[y]]];
    if(x==y) return x;
    for(int i=lg[depth[x]];~i;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}

int ans[N];
void get_ans(int u) {
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].v;
        if(v==fa[u][0]) continue;
        get_ans(v);
        root[u]=SMT.merge(root[u],root[v],1,MAXN);
    }
    ans[u]=SMT.ask(root[u]);
}

int n,m;
void init() {
    lg[0]=-1;
    for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
    dfs(1);
}

int main() {
    n=read(),m=read();
    for(int i=1;i<n;i++) {
        int u,v;
        u=read(),v=read();
        add(u,v),add(v,u);
    }

    init();
    while(m--) {
        int x,y,z,lca;
        x=read(),y=read(),z=read();
        lca=LCA(x,y);
        SMT.change(root[x],1,MAXN,z,1);
        SMT.change(root[y],1,MAXN,z,1);
        SMT.change(root[lca],1,MAXN,z,-1);
        SMT.change(root[fa[lca][0]],1,MAXN,z,-1);
    }
    get_ans(1);

    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);

    return 0;
}

代码（树剖）

#include<bits/stdc++.h>
#define N 100010
#define MAXN 100000

using namespace std;

inline int read() {
    int w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int head[N],tot=0;
struct graph{
    int v,next;
}edge[N<<1];
inline void add(int u,int v) {
    edge[++tot].v=v;
    edge[tot].next=head[u];
    head[u]=tot;
}
class SegmengTree{
  private:
    int n[N<<2],id[N<<2];
    #define n(x) n[x]
    #define id(x) id[x]
    #define ls (p<<1)
    #define rs (ls|1)
    #define mid (l+r>>1)
    inline void update(int p) {
        if(n(ls)>=n(rs)) n(p)=n(ls),id(p)=id(ls);
        else n(p)=n(rs),id(p)=id(rs);
    }
  public:
    void change(int p,int l,int r,int x,int y) {
        if(l==r) {
            n(p)+=y;
            id(p)=l;
            if(!n(p)) id(p)=0;
            return ;
        }
        if(x<=mid) change(ls,l,mid,x,y);
        else change(rs,mid+1,r,x,y);
        update(p);
    }
    int ask() {return id(1);}
}SMT;

int now=0,depth[N],fa[N],size[N],son[N],id[N],rk[N],top[N];
void dfs_first(int u) {
    depth[u]=depth[fa[u]]+1;
    size[u]=1;
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].v;
        if(v==fa[u]) continue;
        fa[v]=u;
        dfs_first(v);
        if(size[v]>size[son[u]]) son[u]=v;
        size[u]+=size[v];
    }
}
void dfs_second(int u,int t) {
    if(!u) return ;
    id[u]=++now;
    rk[now]=u;
    top[u]=t;
    dfs_second(son[u],t);
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].v;
        if(v!=fa[u]&&v!=son[u]) dfs_second(v,v);
    }
}

vector< pair<int,int> > op[N];
void change(int x,int y,int z) {
    op[id[x]].push_back(make_pair(z,1));
    op[id[y]+1].push_back(make_pair(z,-1));
}
void update(int x,int y,int z) {
    while(top[x]!=top[y]) {
        if(depth[top[x]]<depth[top[y]]) swap(x,y);
        change(top[x],x,z);
        x=fa[top[x]];
    }
    if(id[x]>id[y]) swap(x,y);
    change(x,y,z);
}

void init() {
    depth[0]=-1;
    dfs_first(1);
    dfs_second(1,1);
}

int n,m,ans[N];

int main() {
    n=read(),m=read();
    for(int i=1;i<n;i++) {
        int u,v;
        u=read(),v=read();
        add(u,v),add(v,u);
    }

    init();
    while(m--) {
        int x,y,z;
        x=read(),y=read(),z=read();
        update(x,y,z);
    }
    for(int i=1;i<=n;i++) {
        int len=op[i].size();
        for(int j=0;j<len;j++) SMT.change(1,1,MAXN,op[i][j].first,op[i][j].second);
        ans[rk[i]]=SMT.ask();
    }

    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);

    return 0;
}