結果

問題 No.902 Query ζone
ユーザー chocorusk
提出日時 2019-10-07 01:23:53
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,637 ms / 5,000 ms
コード長 5,443 bytes
コンパイル時間 1,987 ms
コンパイル使用メモリ 144,128 KB
実行使用メモリ 36,008 KB
最終ジャッジ日時 2024-10-11 22:48:20
合計ジャッジ時間 23,482 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, ll> P;
template<typename Monoid=int>
struct LinkCutTree{
    using F=function<Monoid(Monoid, Monoid)>;
    using S=function<Monoid(Monoid)>;
    struct Node{
        Node *l, *r, *p;
        int idx;
        Monoid key, sum;
        bool rev;
        int sz;
        bool is_root(){
            return !p || (p->l!=this && p->r!=this);
        }
        Node(int idx, const Monoid &key):idx(idx), key(key), sum(key), sz(1), l(nullptr), r(nullptr), p(nullptr), rev(false) {}
    };
    const Monoid M1;
    const F f;
    const S s;
    LinkCutTree():LinkCutTree([](Monoid a, Monoid b){ return a+b;}, [](Monoid a){ return a;}, Monoid()){}
    LinkCutTree(const F &f, const S &s, const Monoid &M1):f(f), s(s), M1(M1){}
    Node *make_node(int idx, const Monoid &v=Monoid()){
        return new Node(idx, v);
    }
    void toggle(Node *t){
        assert(t);
        swap(t->l, t->r);
        t->sum=s(t->sum);
        t->rev^=true;
    }
    void push(Node *t){
        if(t->rev){
            if(t->l) toggle(t->l);
            if(t->r) toggle(t->r);
            t->rev=false;
        }
    }
    void update(Node *t){
        t->sz=1;
        t->sum=t->key;
        if(t->l) t->sz+=t->l->sz, t->sum=f(t->l->sum, t->sum);
        if(t->r) t->sz+=t->r->sz, t->sum=f(t->sum, t->r->sum);
    }
    void rotr(Node *t){
        auto *x=t->p, *y=x->p;
        if((x->l=t->r)) t->r->p=x;
        t->r=x, x->p=t;
        update(x), update(t);
        if((t->p=y)){
            if(y->l==x) y->l=t;
            if(y->r==x) y->r=t;
            update(y);
        }
    }
    void rotl(Node *t){
        auto *x=t->p, *y=x->p;
        if((x->r=t->l)) t->l->p=x;
        t->l=x, x->p=t;
        update(x), update(t);
        if((t->p=y)){
            if(y->l==x) y->l=t;
            if(y->r==x) y->r=t;
            update(y);
        }
    }
    void splay(Node* t){
        push(t);
        while(!t->is_root()){
            auto *q=t->p;
            if(q->is_root()){
                push(q), push(t);
                if(q->l==t) rotr(t);
                else rotl(t);
            }else{
                auto *r=q->p;
                push(r), push(q), push(t);
                if(r->l==q){
                    if(q->l==t) rotr(q), rotr(t);
                    else rotl(t), rotr(t);
                }else{
                    if(q->r==t) rotl(q), rotl(t);
                    else rotr(t), rotl(t);
                }
            }
        }
    }
    Node *expose(Node *t){
        Node *rp=nullptr;
        for(Node *cur=t; cur; cur=cur->p){
            splay(cur);
            cur->r=rp;
            update(cur);
            rp=cur;
        }
        splay(t);
        return rp;
    }
    void link(Node *child, Node *parent){
        expose(child);
        expose(parent);
        child->p=parent;
        parent->r=child;
        update(parent);
    }
    void cut(Node *child){
        expose(child);
        auto *parent=child->l;
        child->l=nullptr;
        parent->p=nullptr;
        update(child);
    }
    void evert(Node *t){
        expose(t);
        toggle(t);
        push(t);
    }
    Node *lca(Node *u, Node *v){
        //if(get_root(u)!=get_root(v)) return nullptr;
        expose(u);
        return expose(v);
    }
    Node *get_root(Node *x){
        expose(x);
        while(x->l){
            push(x);
            x=x->l;
        }
        return x;
    }
    Node *get_kth(Node *v, int k){
        expose(v);
        while(v){
            push(v);
            if(v->r && v->r->sz>k){
                v=v->r;
            }else{
                if(v->r) k-=v->r->sz;
                if(k==0) return v;
                k--;
                v=v->l;
            }
        }
        return nullptr;
    }
    bool comp(Node *u, Node *v, int du, int dv){
        auto *p=lca(u, v);
        if(p==u) return true;
        else if(p==v) return false;
        expose(p);
        int d=p->sum.first;
        return get_kth(u, 2*(du-d-1))->idx < get_kth(v, 2*(dv-d-1))->idx;
    }
};
int a[100010], b[100010]; ll w[100010];
int main()
{
    int n;
    scanf("%d", &n);
    using LCT=LinkCutTree<P>;
    auto f=[](P a, P b){ return P(a.first+b.first, a.second+b.second);};
    LCT lct(f, [](P a){ return a;}, P(0, 0));
    vector<LCT::Node*> nodev(n), nodee(n-1);
    for(int i=0; i<n; i++){
        nodev[i]=lct.make_node(i, P(0, 0));
    }
    vector<vector<P>> g(n);
    map<P, int> mp;
    for(int i=0; i<n-1; i++){
        scanf("%d %d %lld", &a[i], &b[i], &w[i]);
        if(a[i]>b[i]) swap(a[i], b[i]);
        mp[{a[i], b[i]}]=i;
        g[a[i]].push_back({b[i], i});
        g[b[i]].push_back({a[i], i});
        nodee[i]=lct.make_node(n+i, P(1, w[i]));
    }
    auto dfs=[&](auto dfs, int u, int p)->void{
        for(auto q:g[u]){
            if(q.first==p) continue;
            lct.link(nodee[q.second], nodev[u]);
            lct.link(nodev[q.first], nodee[q.second]);
            dfs(dfs, q.first, u);
        }
    };
    dfs(dfs, 0, -1);
    int Q;
    scanf("%d", &Q);
    for(int i=0; i<Q; i++){
        int t=2;
        scanf("%d", &t);
        if(t==1){
            int ui, vi, wi; ll xi;
            scanf("%d %d %d %lld", &ui, &vi, &wi, &xi);
            int e;
            if(ui>vi){
                e=mp[{vi, ui}];
                mp.erase({vi, ui});
            }else{
                e=mp[{ui, vi}];
                mp.erase({ui, vi});
            }
            lct.evert(nodev[vi]);
            lct.cut(nodev[ui]);
            nodee[e]->key=P(1, xi);
            lct.evert(nodev[wi]);
            lct.link(nodev[wi], nodee[e]);
            if(vi>wi) swap(vi, wi);
            mp[{vi, wi}]=e;
        }else{
            int k;
            scanf("%d", &k);
            vector<int> vx(k), ind(k);
            vector<int> vd(k);
            for(int j=0; j<k; j++){
                scanf("%d", &vx[j]);
                ind[j]=j;
                lct.expose(nodev[vx[j]]);
                vd[j]=nodev[vx[j]]->sum.first;
            }
            sort(ind.begin(), ind.end(), [&](int x, int y){ return lct.comp(nodev[vx[x]], nodev[vx[y]], vd[x], vd[y]);});
            ll ans=0;
            for(int j=0; j<k; j++){
                int x=vx[ind[j]], y;
                if(j==k-1) y=vx[ind[0]];
                else y=vx[ind[j+1]];
                lct.evert(nodev[x]);
                lct.expose(nodev[y]);
                ans+=nodev[y]->sum.second;
            }
            ans/=2;
            printf("%lld\n", ans);
        }
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0