#1173766 (C++23) No.399 動的な領主

• 問題: No.399 動的な領主
• ユーザー: ZeriToki
• 提出日時: 2026-07-26 16:50:17
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 800 ms / 2,000 ms
• コード長: 6,786 bytes
• コンパイル時間: 4,085 ms
• コンパイル使用メモリ: 363,620 KB
• 実行使用メモリ: 30,096 KB
• 最終ジャッジ日時: 2026-07-26 16:52:14
• 合計ジャッジ時間: 11,854 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
other	AC * 19

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
const long long mod=998244353;
const long long mod2=469762049;
const long long mod100=1000000007;
struct HLD{
    //0-indexed
    //根が0の根付き木で実装
    vector<int>V;//入りがけ順
    vector<int>id;//頂点iがどこにあるか
    vector<int>head;//頂点iが属するheavy pathの親
    vector<int>child;//頂点iが属するheavy pathの子
    vector<vector<int>>G;//グラフ
    vector<int>subtree;//部分木サイズ
    vector<int>parent;

    //初期化
    HLD(int N){
        id.assign(N,-1);
        head.assign(N,-1);
        child.assign(N,-1);
        subtree.assign(N,-1);
        parent.assign(N,-1);
        G.assign(N,{});
    }

    //辺の追加
    void add_edge(int u,int v){
        G[u].push_back(v);
        G[v].push_back(u);
    }

    //テーブルの作成。辺を追加した後にやる
    void make_table(){
        auto dfs1=[&](auto &dfs1,int pos,int last)->void {
            subtree[pos]=1;
            for(auto nex:G[pos]){
                if(nex==last) continue;
                parent[nex]=pos;
                dfs1(dfs1,nex,pos);
                subtree[pos]+=subtree[nex];
            }
            return;
        };
        dfs1(dfs1,0,-1);
        auto dfs2=[&](auto &dfs2,int pos,int last,int h)->int {
            id[pos]=(int)V.size();
            V.push_back(pos);
            head[pos]=h;
            pair<int,int>priority={-1,-1};
            for(auto nex:G[pos]){
                if(nex==last) continue;
                chmax(priority,{subtree[nex],nex});
            }
            if(priority.second==-1){
                child[pos]=pos;
                return pos;
            }
            child[pos]=dfs2(dfs2,priority.second,pos,h);
            for(auto nex:G[pos]){
                if(nex==last) continue;
                if(priority.second==nex) continue;
                dfs2(dfs2,nex,pos,nex);
            }
            return child[pos];
        };
        dfs2(dfs2,0,-1,0);
        return;
    }
    int LCA(int u,int v){
        while(true){
            if(head[u]==head[v]){
                if(id[u]>id[v]) return v;
                else return u;
            }
            if(id[u]>id[v]){
                u=parent[head[u]];
            }
            else{
                v=parent[head[v]];
            }
        }
    }
};

template<typename T,typename F> struct lazysegtree{
    using F1=function<T(T,T)>;
    using F2=function<T(T,F)>;
    using F3=function<F(F,F)>;
    vector<T>node;
    vector<F>lazy;
    int N;int log;F1 op;T e;F2 mapping;F3 composition;F id;
    lazysegtree(int n,F1 op,T e,F2 mapping,F3 composition,F id)
    :op(op),e(e),mapping(mapping),composition(composition),id(id){
        N=1;
        log=1;
        while(N<n){
            N<<=1;
            log++;
        }
        node.assign(N*2,e);
        lazy.assign(N*2,id);
    }
    void set(int p,T x){
        int pos=1;
        for(int i=log-2;i>=0;i--){
            lazy[pos*2]=composition(lazy[pos*2],lazy[pos]);
            lazy[pos*2+1]=composition(lazy[pos*2+1],lazy[pos]);
            node[pos*2]=mapping(node[pos*2],lazy[pos]);
            node[pos*2+1]=mapping(node[pos*2+1],lazy[pos]);
            lazy[pos]=id;
            pos<<=1;
            if((p>>i)&1) pos++;
        }
        lazy[pos]=id;
        node[pos]=x;
        while(pos>=2){
            pos/=2;
            node[pos]=op(node[pos*2],node[pos*2+1]);
        }
        return;
    }
    void apply(int l,int r,int a,int b,int u,F f){
        if(b<=l || r<=a) return;
        if(l<=a && b<=r){
            lazy[u]=composition(lazy[u],f);
            node[u]=mapping(node[u],f);
            return;
        }
        lazy[u*2]=composition(lazy[u*2],lazy[u]);
        lazy[u*2+1]=composition(lazy[u*2+1],lazy[u]);
        node[u*2]=mapping(node[u*2],lazy[u]);
        node[u*2+1]=mapping(node[u*2+1],lazy[u]);
        lazy[u]=id;
        int m=(a+b)/2;
        apply(l,r,a,m,u*2,f);
        apply(l,r,m,b,u*2+1,f);
        node[u]=op(node[u*2],node[u*2+1]);
        return;
    }
    void apply(int l,int r,F f){//[l,r)を変更
        l++;r++;
        apply(l,r,1,N+1,1,f);
    }
    void apply(int p,F f){
        apply(p,p+1,1,N+1,1,f);
    }
    T fold(int l,int r,int a,int b,int u){
        if(b<=l || r<=a)return e;
        if(l<=a && b<=r){
            return node[u];
        }
        int m=(a+b)/2;
        T L=mapping(fold(l,r,a,m,u*2),lazy[u]);
        T R=mapping(fold(l,r,m,b,u*2+1),lazy[u]);
        return op(L,R);
    }
    T fold(int l,int r){//[l,r)をを求める
        l++;r++;
        return fold(l,r,1,N+1,1);
    }
    T fold(int p){
        p++;
        return fold(p,p+1,1,N+1,1);
    }
};

struct S{
    ll siz,ans;
};
S e(){
    S res;
    res.siz=0;
    res.ans=0;
    return res;
}
S op(S a,S b){
    S res;
    res.siz=a.siz+b.siz;
    res.ans=a.ans+b.ans;
    return res;
}
S mapping(S x,ll f){
    x.ans+=f*x.siz;
    return x;
}
ll composition(ll f,ll g){
    return f+g;
}
int main(){
    cout.tie()->sync_with_stdio(0);
    cin.tie(0);
    
    int N;cin>>N;
    int u[N-1],v[N-1];
    for(int i=0;i<N-1;i++){
        cin>>u[i]>>v[i];
        u[i]--;v[i]--;
    }
    int Q;cin>>Q;
    int A[Q],B[Q];
    for(int i=0;i<Q;i++){
        cin>>A[i]>>B[i];
        A[i]--;B[i]--;
    }


    HLD H(N);
    for(int i=0;i<N-1;i++){
        H.add_edge(u[i],v[i]);
    }
    H.make_table();
    lazysegtree<S,ll>seg(N,op,e(),mapping,composition,0LL);

    for(int i=0;i<N;i++){
        S now;
        now.siz=1;
        now.ans=1;
        seg.set(i,now);
    }


    auto solve=[&](int a,int b){
        ll res=0;
        int c=H.LCA(a,b);
        while(true){
            if(H.head[a]==H.head[c]){
                res+=seg.fold(H.id[c],H.id[a]+1).ans;
                seg.apply(H.id[c],H.id[a]+1,1);
                break;
            }
            int goal=H.head[a];
            res+=seg.fold(H.id[goal],H.id[a]+1).ans;
            seg.apply(H.id[goal],H.id[a]+1,1);
            a=H.parent[goal];
        }
        while(true){
            if(H.head[b]==H.head[c]){
                res+=seg.fold(H.id[c]+1,H.id[b]+1).ans;
                seg.apply(H.id[c]+1,H.id[b]+1,1);
                break;
            }
            int goal=H.head[b];
            res+=seg.fold(H.id[goal],H.id[b]+1).ans;
            seg.apply(H.id[goal],H.id[b]+1,1);
            b=H.parent[goal];
        }
        return res;
    };

    ll ans=0;
    for(int i=0;i<Q;i++){
        ans+=solve(A[i],B[i]);
    }
    cout<<ans<<endl;
}