結果

問題 No.399 動的な領主
ユーザー mugen_1337mugen_1337
提出日時 2021-04-26 21:14:01
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 7,565 bytes
コンパイル時間 2,616 ms
コンパイル使用メモリ 212,936 KB
実行使用メモリ 10,704 KB
最終ジャッジ日時 2023-09-18 16:58:15
合計ジャッジ時間 7,374 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x),end(x)
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;

template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
    return os;
}
template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(T &x:v)is>>x;
    return is;
}

/*
pushでlazy valueを押し付ければよい

Flipは普通にMonoid(Monoid)でいい気がする
常に，swapした後にLazy Valueをおろせばいいので
*/


template<typename Monoid,typename OperatorMonoid=Monoid>
struct LazyLinkCutTree{

    using F=function<Monoid(Monoid,Monoid)>;
    using G=function<Monoid(Monoid,OperatorMonoid)>;
    using H=function<OperatorMonoid(OperatorMonoid,OperatorMonoid)>;
    using Flip=function<Monoid(Monoid)>;

    LazyLinkCutTree(int n,F f,G g,H h,Monoid e,OperatorMonoid oe,Flip flip=nullptr)
    :f(f),g(g),h(h),e(e),oe(oe),flip(flip){
        for(int i=0;i<n;i++) nodes.push_back(new Node(e,oe,i));
    }

    LazyLinkCutTree(const vector<Monoid> &v,F f,G g,H h,Monoid e,OperatorMonoid oe,Flip flip=nullptr)
    :f(f),g(g),h(h),e(e),oe(oe),flip(flip){
        for(int i=0;i<(int)v.size();i++) nodes.push_back(new Node(v[i],oe,i));
    }

    // v を root に
    void evert(int v){
        expose(nodes[v]);
        reverse(nodes[v]);
    }

    // link
    void link(int ch,int par){
        evert(ch);
        expose(nodes[par]);
        nodes[ch]->p=nodes[par];
        nodes[par]->r=nodes[ch];
        recalc(nodes[par]);
    }

    // cut v-(v->p)
    void cut(int v){
        expose(nodes[v]);
        nodes[v]->l->p=nullptr;
        nodes[v]->l=nullptr;
        recalc(nodes[v]);
    }
    // check u-v in E, cut u-v
    void cut(int u,int v){
        evert(u);
        expose(nodes[v]);
        assert(nodes[u]==nodes[v]->l);
        nodes[v]->l->p=nullptr;
        nodes[v]->l=nullptr;
        recalc(nodes[v]);
    }


    Monoid query(int u,int v){
        evert(u);
        expose(nodes[v]);
        return nodes[v]->sum;
    }

    void update(int u,int v,OperatorMonoid x){
        evert(u);
        expose(nodes[v]);
        nodes[v]->lazy=h(nodes[v]->lazy,x);
    }
    
    int get_root(int v){
        Node *cur=nodes[v];
        expose(cur);
        while(cur->l){
            push(cur);
            cur=cur->l;
        }
        splay(cur);
        return cur->idx;
    }
    
    // not connected -> return -1
    int lca(int u,int v){
        if(!is_connected(u,v)) return -1;
        expose(nodes[u]);
        return expose(nodes[v]);
    }

    // faster than get_root(u)==get_root(v)
    bool is_connected(int u,int v){
        if(u==v) return true;
        expose(nodes[u]);
        expose(nodes[v]);
        return bool(nodes[u]->p);
    }

    // 未verify
    int depth(int v){
        expose(nodes[v]);
        return size(nodes[v])-1;
    }
    // 未verify
    // ヤバかったらpath queryで各頂点1をのせろ
    int distance(int u,int v){
        int p=lca(u,v);
        if(p<0) return -1;
        return depth(u)+depth(v)-depth(p)*2;
    }
    
private:
    struct Node{
        Node *l,*r,*p;
        Monoid val,sum;
        OperatorMonoid lazy;
        int sz,idx;
        bool rev;
        bool is_root()const{
            return (!p or (p->l!=(this) and p->r!=(this)));
        }
        Node(const Monoid &x,const OperatorMonoid &y,int idx)
            :l(nullptr),r(nullptr),p(nullptr),
            val(x),sum(x),lazy(y),sz(1),idx(idx),rev(false){}
    };

    const F f;
    const G g;
    const H h;
    const Monoid e;
    const OperatorMonoid oe;
    const Flip flip;
    vector<Node *> nodes;

    int expose(Node *t){
        Node *pre=nullptr;
        for(Node *cur=t;cur;cur=cur->p){
            splay(cur);
            cur->r=pre;
            recalc(cur);
            pre=cur;
        }
        splay(t);
        return pre->idx;
    }
    // tを1個下へ
    void rotr(Node *t){
        // ((A) - lch - (B)) - t - (C) 
        Node *lch=t->l;// lch->top
        t->l=lch->r;
        if(lch->r) lch->r->p=t;// B
        lch->p=t->p;
        if(t->p){
            if(t->p->l==t) t->p->l=lch;
            if(t->p->r==t) t->p->r=lch;
        }
        lch->r=t;
        t->p=lch;
        recalc(t);
        recalc(lch);
    }
    void rotl(Node *t){
        // (C) - t - ((B) - rch - (A) )
        Node *rch=t->r;// lch->top
        t->r=rch->l;
        if(rch->l) rch->l->p=t;// B
        rch->p=t->p;
        if(t->p){
            if(t->p->l==t) t->p->l=rch;
            if(t->p->r==t) t->p->r=rch;
        }
        rch->l=t;
        t->p=rch;
        recalc(t);
        recalc(rch);
    }

    int size(Node *t) const { return (t?t->sz:0); }

    void recalc(Node *t){
        if(!t) return ;
        t->sz=size(t->l)+1+size(t->r);
        t->sum=t->val;
        if(t->l){
            push(t->l);
            t->sum=f(t->l->sum,t->sum);
        }
        if(t->r){
            push(t->r);
            t->sum=f(t->sum,t->r->sum);
        }
    }

    void push(Node *t){
        if(t->lazy!=oe){
            t->val=g(t->val,t->lazy);
            if(t->l) t->l->lazy=h(t->l->lazy,t->lazy);
            if(t->r) t->r->lazy=h(t->r->lazy,t->lazy);
            t->lazy=oe;
        }

        if(t->rev){
            if(t->l) reverse(t->l);
            if(t->r) reverse(t->r);
            t->rev=false;
        }
    }

    void reverse(Node *t){
        swap(t->l,t->r);
        if(flip) t->sum=flip(t->sum);
        t->rev^=true;
    }
    
    void splay(Node *cur){
        push(cur);
        while(!cur->is_root()){
            Node *par=cur->p;
            if(par->is_root()){// zig
                push(par);
                push(cur);
                if(par->l==cur) rotr(par);
                else            rotl(par);
            }else{// zig-zig, zig-zag
                Node *parpar=par->p;
                push(parpar);
                push(par);
                push(cur);
                if(cur==par->l){
                    if(par==parpar->l){
                        rotr(parpar);
                        rotr(par);
                    }else{
                        rotr(par);
                        rotl(parpar);
                    }
                }else{
                    if(par==parpar->l){
                        rotl(par);
                        rotr(parpar);
                    }else{
                        rotl(parpar);
                        rotl(par);
                    }
                }
            }
        }
    }
};

signed main(){
    int n;cin>>n;

    auto f=[&](int a,int b){
        return a+b;
    };

    vector<int> ones(n,1);
    LazyLinkCutTree<int,int> lct(ones,f,f,f,0,0);

    rep(i,n-1){
        int u,v;cin>>u>>v;u--,v--;
        lct.link(u,v);
    }

    int q;cin>>q;
    ll ans=0;
    while(q--){
        int a,b;cin>>a>>b;a--,b--;
        ans+=lct.query(a,b);
        lct.update(a,b,1);
    }
    cout<<ans<<endl;
    return 0;
}
0