#651673 (C++17) No.399 動的な領主

• 問題: No.399 動的な領主
• ユーザー: mugen_1337
• 提出日時: 2021-04-27 00:08:56
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 658 ms / 2,000 ms
• コード長: 7,299 bytes
• コンパイル時間: 2,667 ms
• コンパイル使用メモリ: 212,776 KB
• 実行使用メモリ: 14,920 KB
• 最終ジャッジ日時: 2023-09-19 03:52:27
• 合計ジャッジ時間: 10,022 ms
• ジャッジサーバーID （参考情報）: judge11 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,376 KB
testcase_01	AC	2 ms; 4,380 KB
testcase_02	AC	2 ms; 4,380 KB
testcase_03	AC	2 ms; 4,376 KB
testcase_04	AC	4 ms; 4,376 KB
testcase_05	AC	39 ms; 4,416 KB
testcase_06	AC	658 ms; 14,920 KB
testcase_07	AC	642 ms; 14,916 KB
testcase_08	AC	610 ms; 14,852 KB
testcase_09	AC	613 ms; 14,776 KB
testcase_10	AC	5 ms; 4,376 KB
testcase_11	AC	26 ms; 4,384 KB
testcase_12	AC	332 ms; 14,840 KB
testcase_13	AC	306 ms; 14,792 KB
testcase_14	AC	78 ms; 14,920 KB
testcase_15	AC	362 ms; 14,796 KB
testcase_16	AC	418 ms; 14,792 KB
testcase_17	AC	620 ms; 14,784 KB
testcase_18	AC	612 ms; 14,780 KB

ソースコード

#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]);
        propagate(nodes[v],x);
        push(nodes[v]);
    }
    
    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;
    }
    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;
        recalc(x);
        recalc(t);
        if((t->p=y)){
            if(y->l==x) y->l=t;
            if(y->r==x) y->r=t;
            recalc(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;
        recalc(x);
        recalc(t);
        if((t->p=y)){
            if(y->l==x) y->l=t;
            if(y->r==x) y->r=t;
            recalc(y);
        }
    }

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

    void recalc(Node *t){
        t->sum=t->val;
        if(t->l) t->sum=f(t->l->sum,t->sum);
        if(t->r) t->sum=f(t->sum,t->r->sum);
    }

    void propagate(Node *t,OperatorMonoid x){
        t->lazy=h(t->lazy,x);
        t->val=g(t->val,x);
        t->sum=g(t->sum,x);
    }

    void push(Node *t){
        if(t->lazy!=oe){
            if(t->l) propagate(t->l,t->lazy);
            if(t->r) propagate(t->r,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(cur);
                else            rotl(cur);
            }else{// zig-zig, zig-zag
                Node *parpar=par->p;
                push(parpar);
                push(par);
                push(cur);
                if(parpar->l==par){
                    if(par->l==cur){rotr(par);rotr(cur);}
                    else           {rotl(cur);rotr(cur);}
                }else{
                    if(par->r==cur){rotl(par);rotl(cur);}
                    else           {rotr(cur);rotl(cur);}
                }
            }
        }
    }
};

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

    auto f=[&](pair<ll,ll> a,pair<ll,ll> b){
        return make_pair(a.first+b.first,a.second+b.second);
    };
    auto g=[&](pair<ll,ll> a,ll b){
        return make_pair(a.first+a.second*b,a.second);
    };
    auto h=[&](ll a,ll b){
        return a+b;
    };

    vector<pair<ll,ll>> ones(n,{1,1});
    LazyLinkCutTree<pair<ll,ll>,ll> lct(ones,f,g,h,{0,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).first;
        lct.update(a,b,1);
    }
    cout<<ans<<endl;
    return 0;
}