結果

問題 No.399 動的な領主
ユーザー momoyuumomoyuu
提出日時 2023-03-21 21:03:01
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,097 ms / 2,000 ms
コード長 3,843 bytes
コンパイル時間 3,465 ms
コンパイル使用メモリ 263,240 KB
実行使用メモリ 23,552 KB
最終ジャッジ日時 2024-09-18 14:30:50
合計ジャッジ時間 13,292 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

template< typename T1, typename T2 = T1 >
struct lazysegtree{
    using F1 = function<T1(T1,T1)>;
    using F2 = function<T2(T2,T2)>;
    //using F3 = function<T1(T2,T1)>;
    using F3 = function<T1(T2,T1,int,int)>;
    int n;
    F1 f1;
    F2 f2;
    F3 f3;
    T1 e1;
    T2 e2,e3;
    vector<T1> data;
    vector<T2> lazy;//莨晄成繝・・繧ｿ
    vector<int> p;//莨晄成縺ｮ繝輔Λ繧ｰW
    /*
     * n:鬆らせ謨ｰ
     * f1:隕∫ｴ蜷悟｣ｫ縺ｮ貍皮ｮ・f2:菴懃畑邏蜷悟｣ｫ,f3:菴懃畑
     * e:蜊倅ｽ榊・
     */
    lazysegtree(int _n,F1 f1,F2 f2,F3 f3,T1 e1,T2 e2,T2 e3):f1(f1),f2(f2),f3(f3),e1(e1),e2(e2),e3(e3){
        n = 1;
        while(n<_n) n<<=1;
        data.assign(2*n,e1);
        lazy.assign(2*n,e3);
        p.assign(2*n,0);
    }

    void set(int i,T1 x){
        data[i+n-1] = x;
    }


    void build(){
        for(int i = n - 2;i>=0;i--){
            data[i] = f1(data[2*i+1],data[2*i+2]);
        }
    }

    void rangeupdate(T2 x,int a,int b,int ni,int l,int r){
        update(ni,l,r);
        if(b<=l||r<=a) return;
        if(a<=l&&r<=b){
            p[ni] = 1;
            lazy[ni] = f2(x,lazy[ni]);
            update(ni,l,r);
        }else{
            rangeupdate(x,a,b,2*ni+1,l,(l+r)/2);
            rangeupdate(x,a,b,2*ni+2,(l+r)/2,r);
            if(l+1<r) data[ni] = f1(data[2*ni+1],data[2*ni+2]);
        }
    }

    void rangeupdate(T2 x,int a,int b){
        rangeupdate(x,a,b,0,0,n);
    }

    void update(int ni,int l,int r){
        if(!p[ni])return;
        p[ni] = 0;
        //data[ni] = f3(lazy[ni],data[ni]);
        data[ni] = f3(lazy[ni],data[ni],l,r);
        if(l+1<r){
            p[2*ni+1] = 1;
            p[2*ni+2] = 1;
            lazy[2*ni+1] = f2(lazy[ni],lazy[2*ni+1]);
            lazy[2*ni+2] = f2(lazy[ni],lazy[2*ni+2]);
        }
        lazy[ni] = e3;
    }

    T1 query(int a,int b,int ni,int l,int r){
        update(ni,l,r);
        if(b<=l||r<=a) return e1;
        if(a<=l&&r<=b) return data[ni];
        else return f1(query(a,b,2*ni+1,l,(l+r)/2),query(a,b,2*ni+2,(r+l)/2,r));
    }

    T1 query(int a,int b){
        return query(a,b,0,0,n);
    }

    T1 operator[](const int i) const {
        return data[i+n-1];
    }
};


const int mx = 1e5 + 10;
int in[mx],out[mx],par[mx],head[mx],sz[mx];
vector<int> g[mx];
int n;
ll c1(ll a,ll b){
    return a+ b;
}
ll c2(ll a,ll b){
    return a + b;
}
ll c3(ll a,ll b,ll l,ll r){
    return a * (r-l) + b;
}

int sdfs(int ni,int p){
    sz[ni] = 1;
    par[ni] = p;
    if(g[ni].size()&&g[ni][0]==p) swap(g[ni][0],g[ni].back());
    for(auto&to:g[ni]){
        if(to==p) continue;
        sz[ni] += sdfs(to,ni);
        if(sz[to]>sz[g[ni][0]]) swap(to,g[ni][0]);
    }
    return sz[ni];
}

void hdfs(int ni,int p,int&time){
    in[ni] = time++;
    for(auto&to:g[ni]){
        if(to==p) continue;
        head[to] = (g[ni][0]==to?head[ni]:to);
        hdfs(to,ni,time);
    }
    out[ni] = time;
}

int main(){
    cin>>n;
    for(int i = 1;i<n;i++){
        int u,v;
        cin>>u>>v;
        u--;v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    lazysegtree<ll> seg(n,c1,c2,c3,0LL,0LL,0LL);
    seg.rangeupdate(1,0,n);
    sdfs(0,-1);
    int time = 0;
    hdfs(0,-1,time);
    ll ans = 0;
    int q;
    cin>>q;
    while(q--){
        //cout<<q<<endl;
        int u,v;
        cin>>u>>v;
        u--;v--;
        for(;;v=par[head[v]]){
            //cout<<u<<" "<<v<<endl;
            if(in[u]>in[v]) swap(u,v);
            if(head[u]==head[v]) break;
            ans += seg.query(in[head[v]],in[v]+1);
            seg.rangeupdate(1,in[head[v]],in[v]+1);
        }
        ans += seg.query(in[u],in[v]+1);
        seg.rangeupdate(1,in[u],in[v]+1);
    }
    cout<<ans<<endl;
}
0