CF696E

__vector__ · 2024-04-12 14:35:33 · 题解

话说背景里的 Barney 是不是作者本人？

废话

这是我第一道没看题解 AC 的 CF 3000 评分题目，不过是远古时期的树剖板子的一个稍微复杂的实现，同机房的也都切了。

大概用了 2h（包括代码里写完题解），就算是当时去打 CF 现场赛也做不到场切。

正文

考虑每次操作怎么处理更舒适。

正好，树上简单路径操作 + 子树整体操作有现成的模板：树链剖分。

现在要求前 k 优的，但在树上维护主席树似乎不是很好维护，暂不考虑。

那么考虑进行 k 次操作，每次取出最优的物品，并将其删除。

所以说，树剖要支持：求最优的物品；删除一个特定的物品；子树整体加法。

这个就比较板子了，更为详细的记录放到了代码注释里。

/*
@Barney Are you the writter of the competition?
You're so crazy!
But I don't think you'll find the gf.
*/
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int T;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
const int maxn=1e5+5;
int n,m,q;
int c[maxn];
struct Girl{
    ll val;
    int id;
};
Girl mkgr(ll val,int id){
    Girl res;
    res.val=val;
    res.id=id;
    return res;
}
vector<Girl> node_girl[maxn];// 存储每个原始树上节点的 girls，按照 val 从大到小排序，另外此时的第二个 id 是 girl 本身编号，而非树上 id

/*
线段需要查询 barney's dream girl 的最小权重，以及对应在哪个线段树节点（由此，线段树节点编号应该映射到给定树上节点）。
同时需要支持删除单个线段树节点的单个最小权值。
具体地，线段树上每个节点，都记录对应树上节点的最小 girl 的 val，以及最小对应的树上节点编号。
合并时，先根据 val，再根据树上编号进行 ckmn
查询时，用和合并一样的方法就可以，最后根据得到的树上节点编号，查询最后一个 girl 的 id 就可以。

删除时，先看看之前查询到的树上节点编号，将其 girls 的最后一个 pop 掉，然后将书上节点编号其映射到对应线段树编号。
然后递归到线段树该节点，重新建立其对应的最小 girl id，以及对应的树上节点编号
然后 pushup

另外，树剖的时候，应当记录是哪一段的线段树，存在比赛作者的梦中情人，然后最后删除操作就去对应的地方求

增加子树权值的时候，直接更新 val，并记录 lazytag_val 代表子树的 val 要增加多少
还要记录 lazytag_leaf（不用下传），用来记录区间的叶子节点需要增加的值，这个在删除单个叶子节点的最小 girl 的时候，用来更新最新的 val

*/
struct Graph{
    vector<int> g[maxn];
    int dfn[maxn],hs[maxn],dep[maxn],fa[maxn],siz[maxn];
    int dfncnt=0;
    int dfntoid[maxn];
    int top[maxn];
    void dfs1(int u,int _fa){
        siz[u]=1;
        fa[u]=_fa;
        dep[u]=dep[_fa]+1;
        for(int& v:g[u]){
            if(v==_fa)continue;
            dfs1(v,u);
            siz[u]+=siz[v];
            if(siz[v]>siz[hs[u]]){
                hs[u]=v;
            }
        }
    }
    void dfs2(int u,int _top){
        dfn[u]=++dfncnt;
        dfntoid[dfncnt]=u;
        top[u]=_top;
        if(hs[u]){
            dfs2(hs[u],_top);
        }
        for(int& v:g[u]){
            if(v==fa[u]||v==hs[u])continue;
            dfs2(v,v);
        }
    }
    void build(){
        dfs1(1,0);
        dfs2(1,1);
    }
}g;
struct SGT{
    int L[maxn<<2],R[maxn<<2];
    Girl val[maxn<<2];// 每个线段树节点对应的最小 girl 的 val 以及原始树上 id
    ll lazytag_val[maxn<<2];
    ll lazytag_leaf[maxn<<2];
    void pushup(int pos){
        val[pos].val=min(val[pos<<1].val,val[pos<<1|1].val);
        if(val[pos<<1].val!=val[pos<<1|1].val){
            if(val[pos<<1].val<val[pos<<1|1].val){
                val[pos].id=val[pos<<1].id;
            }else{
                val[pos].id=val[pos<<1|1].id;
            }
        }else{
            val[pos].id=min(val[pos<<1].id,val[pos<<1|1].id);
        }
    }
    void build(int pos,int l,int r){
        L[pos]=l,R[pos]=r;
   //     printf("pos = %d l = %d r = %d\n",pos,l,r);
        if(l==r){
            if(node_girl[g.dfntoid[l]].empty()){
                val[pos]=mkgr(1e18,1e9);
            }
            else val[pos]=mkgr(node_girl[g.dfntoid[l]].back().val,g.dfntoid[l]);
        //    printf("l = %d r = %d val = [%lld, %d]\n",l,r,val[pos].val,val[pos].id);
            return;
        }
        int mid=((l+r)>>1);
        build(pos<<1,l,mid);
        build(pos<<1|1,mid+1,r);
        pushup(pos);
       // printf("l = %d r = %d val = [%lld, %d]\n",l,r,val[pos].val,val[pos].id);
    }
    void add(int pos,ll _val){
        val[pos].val+=_val;
        lazytag_val[pos]+=_val;
    }
    void pushdown(int pos){
        if(lazytag_val[pos]){
            add(pos<<1,lazytag_val[pos]);
            add(pos<<1|1,lazytag_val[pos]);
            lazytag_val[pos]=0;
        }
    }
    void chg(int pos,int l,int r,ll _val){
        if(L[pos]>=l&&R[pos]<=r){
            add(pos,_val);
            lazytag_leaf[pos]+=_val;
            return;
        }
        if(R[pos]<l||L[pos]>r)return;
        pushdown(pos);
        int mid=((L[pos]+R[pos])>>1);
        if(mid>=l)chg(pos<<1,l,r,_val);
        if(mid<r)chg(pos<<1|1,l,r,_val);
        pushup(pos);
    }
    Girl query(int pos,int l,int r){
        if(L[pos]>=l&&R[pos]<=r){

            return val[pos];
        }
        if(R[pos]<l||L[pos]>r){
            return mkgr(1e18,1e9);
        }
        pushdown(pos);
        Girl res=mkgr(1e18,1e9);
        int mid=(L[pos]+R[pos]>>1);
        if(mid>=l)res=query(pos<<1,l,r);
        if(mid<r){
            Girl tmp=query(pos<<1|1,l,r);
            if(res.val>tmp.val){
                res=tmp;
            }else if(res.val==tmp.val){
                ckmn(res.id,tmp.id);
            }
        }
        return res;
    }
    void del(int pos,int x,ll lazyleafsum){
        lazyleafsum+=lazytag_leaf[pos];
        // 删除 x 位置的最后一个 girl，另外注意，这个 x 是 dfn=x
        if(L[pos]==x&&R[pos]==x){
            node_girl[g.dfntoid[x]].pop_back();
            if(node_girl[g.dfntoid[x]].empty()){
                val[pos]=mkgr(1e18,1e9);
            }else{
                val[pos]=mkgr(node_girl[g.dfntoid[x]].back().val+lazyleafsum,g.dfntoid[x]);
            }
            return;
        }
        if(R[pos]<x||L[pos]>x)return;
        pushdown(pos);
        int mid=(L[pos]+R[pos]>>1);
        if(mid>=x)del(pos<<1,x,lazyleafsum);
        if(mid<x)del(pos<<1|1,x,lazyleafsum);
        pushup(pos);
    }
    vector<int> op1ans;
    void OP1(int a,int b){
        // a,b 简单路径上查询最优 girl，
        Girl dreamgirl=mkgr(1e18,1e9);
        while(g.top[a]!=g.top[b]){
         //   printf("a = %d b=  %d\n",a,b);
            if(g.dep[g.top[a]]<g.dep[g.top[b]])swap(a,b);
            Girl tmp=query(1,g.dfn[g.top[a]],g.dfn[a]);
            if(tmp.val<dreamgirl.val){
                dreamgirl=tmp;
            }else if((tmp.val==dreamgirl.val)&&(tmp.id<dreamgirl.id)){
                dreamgirl=tmp;
            }
            a=g.fa[g.top[a]];
        }
  //      puts("???1");
        if(g.dep[a]>g.dep[b])swap(a,b);
    //    puts("???2");
    //    printf("a = %d b=  %d query = [%d,%d]\n",a,b,g.dfn[a],g.dfn[b]);
        Girl tmp=query(1,g.dfn[a],g.dfn[b]);
    //    puts("???3");
        if(tmp.val<dreamgirl.val){
            dreamgirl=tmp;
        }else if((tmp.val==dreamgirl.val)&&(tmp.id<dreamgirl.id)){
            dreamgirl=tmp;
        }
        if(dreamgirl.id>n){
            op1ans.emplace_back(-1);
            return;
        }
    //    puts("???4");
   //     printf("dgid = %d\n",dreamgirl.id);
        // dreamgirl.id = 其所在的节点，而不是她本身的编号。
        op1ans.emplace_back(node_girl[dreamgirl.id].back().id);
        // 接下来，将最优 girl 从对应节点删除
        del(1,g.dfn[dreamgirl.id],0);
    }
    void op2(int u,ll _val){
        // u 为根的子树加上 _val
        chg(1,g.dfn[u],g.dfn[u]+g.siz[u]-1,_val);
    }
}sgt;
void solve(){
    scanf("%d%d%d",&n,&m,&q);
    FOR(i,1,n-1){
        int u,to;
        scanf("%d%d",&u,&to);
        g.g[u].emplace_back(to);
        g.g[to].emplace_back(u);
    }
    FOR(i,1,m){
        scanf("%d",&c[i]);
        node_girl[c[i]].emplace_back(mkgr(i,i));
    }
    FOR(i,1,n){
        sort(node_girl[i].begin(),node_girl[i].end(),[&](Girl& a,Girl& b){
            return a.val>b.val;
        });
    }
    g.build();
 //   puts("???");
    sgt.build(1,1,n);

    while(q--){
        int op,a,b,c;
        scanf("%d%d%d",&op,&a,&b);
        if(op==1){
            scanf("%d",&c);
            FOR(i,1,c){
             //   printf("i = %d\n",i);
                sgt.OP1(a,b);
                if(sgt.op1ans.back()==-1){
                    sgt.op1ans.pop_back();
                    break;
                }
            }
            printf("%d ",int(sgt.op1ans.size()));
            for(int& v:sgt.op1ans){
                printf("%d ",v);
            }
            puts("");
            sgt.op1ans.clear();
        }else{
            sgt.op2(a,b);
        }
    }
}
int main()
{
    T=1;
    while(T--){
        solve();
    }
    return 0;
}