WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
BZOJ 3307: 雨天的尾巴
BZOJ 3307: 雨天的尾巴

题目大意

给定一颗树,每次对路径(u, v)上所有点增加一个物品c_i。问当所有操作结束的时候,每一个点持有的最多的物品是什么,如果相同数量求编号小者。

题解

对于一次覆盖询问,我们将其在树上差分。
对于每一个点维护一个权值线段树,表示每个物品持有数量的差分标记。
由下向上进行线段树合并的时候统计答案即可。

代码

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

namespace LCA{
    const int MAXN=1e5+50;
    const int LOGN=20;
    int dep[MAXN], fa[MAXN][LOGN];
    struct Edge{
        int v, nxt;
        Edge(){}
        Edge(int v0, int n0){ v=v0; nxt=n0; }
    }e[MAXN*2];
    int head[MAXN], nume;

    /**
     * Init For LCA
     */
    inline void initEdge() { memset(head, 0, sizeof(head)); nume=0; }

    /**
     * Add Edges
     */
    inline void addEdge(int u, int v){
        e[++nume]=Edge(v, head[u]);
        head[u]=nume;
        e[++nume]=Edge(u, head[v]);
        head[v]=nume;
    }

    /**
     * DFS For LCA
     */
    void dfs(int x, int from){
        dep[x]=dep[fa[x][0]=from]+1;
        for (int i=1; i<LOGN; i++) fa[x][i]=fa[fa[x][i-1]][i-1];
        for (int i=head[x]; i; i=e[i].nxt){
            int v=e[i].v; if (v==from) continue;
            dfs(v, x);
        }
    }

    /**
     * Prepare For LCA
     */
    inline void prepare(){ dep[1]=0; dfs(1, 1); }

    /**
     * Query For LCA
     */
    inline void swim(int &x, int h){ for (int i=0; i<LOGN; i++, h/=2) if (h&1) x=fa[x][i]; }
    int query(int x, int y){
        if (dep[x]<dep[y]) swap(x, y);
        swim(x, dep[x]-dep[y]);
        if (x==y) return x;
        for (int i=LOGN-1; i>=0; i--){
            if (fa[x][i]==fa[y][i]) continue;
            x=fa[x][i]; y=fa[y][i];
        }
        return fa[x][0];
    }
}

namespace STREE{
    #define ls(x) tree[x].lx
    #define rs(x) tree[x].rx
    const int MAXN=1e5+50;
    struct BTree{
        int lx, rx;
        int mx, mp;
    }tree[MAXN*64];
    int nume;

    void update(int x){
        if (rs(x)==0 && ls(x)==0) { tree[x].mp=0; return; }
        if (!rs(x)||!ls(x)){
            tree[x].mx=tree[ls(x)+rs(x)].mx;
            tree[x].mp=tree[ls(x)+rs(x)].mp;
        }
        if (tree[ls(x)].mx>=tree[rs(x)].mx){
            tree[x].mx=tree[ls(x)].mx, tree[x].mp=tree[ls(x)].mp;
        }else{
            tree[x].mx=tree[rs(x)].mx, tree[x].mp=tree[rs(x)].mp;
        }
    }

    void modify(int &x, int l, int r, int p, int v){
        if (!x) {
            x=++nume; ls(x)=rs(x)=0;
            tree[x].mx=tree[x].mp=0;
        }
        if (l==r){
            tree[x].mx+=v;
            tree[x].mp=l;
        }else{
            int m=(l+r)/2;
            if (p<=m) modify(ls(x), l, m, p, v); else modify(rs(x), m+1, r, p, v);
            update(x);
        }
    }

    int merge(int x, int y, int l, int r){
        if (!x || !y) return x+y;
        if (l==r){
            tree[x].mx+=tree[y].mx;
            tree[x].mp=l;
        }else{
            int m=(l+r)/2;
            ls(x)=merge(ls(x), ls(y), l, m);
            rs(x)=merge(rs(x), rs(y), m+1 ,r);
            update(x);
        }
        return x;
    }
}

const int MAXN=1e5+50;
struct OPNode{ int u, v, z; }op[MAXN];
int pool[MAXN], tot;
int n, m;
int rt[MAXN];
int ans[MAXN];

void solve(int x, int from){
    for (int i=LCA::head[x]; i; i=LCA::e[i].nxt){
        int v=LCA::e[i].v; if (v==from) continue;
        solve(v, x);
        rt[x]=STREE::merge(rt[x], rt[v], 0, tot+1);
    }
    if (STREE::tree[rt[x]].mx>0) ans[x]=STREE::tree[rt[x]].mp;
}

int main(){
    scanf("%d%d", &n, &m);
    for (int i=1; i<n; i++){
        int x, y; scanf("%d%d", &x, &y);
        LCA::addEdge(x, y);
    }
    LCA::prepare();

    tot=0;
    for (int i=1; i<=m; i++){
        scanf("%d%d%d", &op[i].u, &op[i].v, &op[i].z);
        pool[++tot]=op[i].z;
    }
    sort(pool+1, pool+tot+1);
    tot=unique(pool+1, pool+tot+1)-pool-1;
    for (int i=1; i<=m; i++) op[i].z=lower_bound(pool+1, pool+tot+1, op[i].z)-pool;

    for (int i=1; i<=m; i++){
        STREE::modify(rt[op[i].u], 0, tot+1, op[i].z, 1);
        STREE::modify(rt[op[i].v], 0, tot+1, op[i].z, 1);
        int f=LCA::query(op[i].u, op[i].v);
        STREE::modify(rt[f], 0, tot+1, op[i].z, -1);
        if (f!=1) STREE::modify(rt[LCA::fa[f][0]], 0, tot+1, op[i].z, -1);
    }

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

    return 0;
}

赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

BZOJ 3307: 雨天的尾巴
题目大意 给定一颗树,每次对路径$(u, v)$上所有点增加一个物品$c_i$。问当所有操作结束的时候,每一个点持有的最多的物品是什么,如果相同数量求编号小者。 题解 对于一次覆盖询问,…
扫描二维码继续阅读
2018-10-16
<--! http2https -->