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

• 問題: No.399 動的な領主
• ユーザー: sorachandu
• 提出日時: 2026-06-04 01:32:00
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 253 ms / 2,000 ms
• コード長: 5,968 bytes
• コンパイル時間: 3,108 ms
• コンパイル使用メモリ: 353,952 KB
• 実行使用メモリ: 24,056 KB
• 最終ジャッジ日時: 2026-06-04 01:32:09
• 合計ジャッジ時間: 6,174 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_1

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
#include<atcoder/lazysegtree>

/*//--------------------------------------------------------
木に対して重軽分解をする構造体
refer:
https://info.atcoder.jp/entry/algorithm_lectures/heavy_light_decomposition
https://nachiavivias.github.io/cp-library/cpp/tree/heavy-light-decomposition.html
*///--------------------------------------------------------
struct HeavyLightDecomposition{
private:
    int N;
    std::vector<int> par;
    std::vector<int> dep;
    std::vector<int> siz;
    std::vector<int> vertex;
    std::vector<int> id;
    std::vector<int> head;

public:
    // G is tree that represented by AdjacencyList
    HeavyLightDecomposition(std::vector<std::vector<int>> G,int root=0){
        N=std::ssize(G);
        par.assign(N,-1);
        dep.assign(N,-1);
        siz.assign(N,0);
        vertex.assign(N,-1);
        id.assign(N,-1);
        head.assign(N,-1);
        {
            // calculate subtree size, put the heave child first in G.
            auto dfs=[&](auto &dfs, int v, int p=-1) -> void {
                par[v]=p;
                dep[v]=(p==-1 ? 0 : dep[p]+1);
                siz[v]=1;
                if(!G[v].empty() and G[v][0]==p) std::swap(G[v][0],G[v].back());
                for(int &w:G[v]){
                    if(w==p) continue;
                    dfs(dfs,w,v);
                    siz[v]+=siz[w];
                    if(siz[w]>siz[G[v][0]]) std::swap(G[v][0],w);
                }
            };
            dfs(dfs,root);
        }
        {
            int idx=0;
            auto dfs=[&](auto &dfs,int v,int p=-1) -> void {
                id[v]=idx;
                vertex[idx++]=v;
                for(int &w:G[v]){
                    if(w==p) continue;
                    bool heavy=(w==G[v][0]);
                    head[w]=(heavy?head[v]:w);
                    dfs(dfs,w,v);
                }
            };
            head[root]=root;
            dfs(dfs,root);
        }
    }

    int numVertices() const { return N; }
    // 頂点vの深さ (dep)
    int depth(int v) const { return dep[v]; }
    // 頂点vがHLD配列上で何番目か (id)
    int toSeq(int v) const { return id[v]; }
    // HLD配列[seqidx]の頂点番号 (vertex)
    int toVertex(int seqidx) const { return vertex[seqidx]; }
    // 頂点vの親 (根なら-1)
    int parent(int v) const { return par[v]; }
    // 頂点vのheavyRoot　(heavyPathに乗っていなければ自身の番号を返す)
    int heavyR(int v) const { return head[v]; }
    // 頂点vのheaveChild　存在しなければ-1
    int heavyC(int v) const {
        if(toSeq(v)==N-1) return -1;
        int cand=toVertex(toSeq(v)+1);
        if(same(v,cand)) return cand;
        return -1;
    }

    // 頂点uと頂点vが同一のheavyPathに乗っているか
    bool same(int u,int v) const { return head[u]==head[v]; }
    // 頂点uと頂点vについてHLD配列上でu<vを成立させる (外部クエリ処理用)
    void normalizePair(int &u,int &v){ if(id[u]>id[v]) swap(u,v); }
    // 頂点vがheavyPath上で何番目の頂点か
    int distToHR(int v) const { return id[v]-id[head[v]]; }
    // 頂点vが含まれるheavyPathを配列で返す stopV=trueでvで止まる
    // O(len(heavyPath))
    std::vector<int> heavyPath(int v,bool stopV=false) const {
        std::vector<int> path;
        int idx=id[head[v]];
        while(idx!=-1){
            path.emplace_back(idx);
            if(stopV and idx==v) break; 
            idx=heavyC(idx);
        }
        return path;
    }
    // Level Ancestor　頂点vの祖先であって深さdにある頂点番号を返す
    // O(logN)
    int LA(int v,int d) const {
        assert(dep[v]>=d);
        while(dep[head[v]]>d){
            v=par[head[v]];
        }
        return vertex[id[v]-(dep[v]-d)];
    }
    // Lowest Common Ancestor　頂点u,vの最近共通祖先なる頂点番号を返す
    // O(logN)
    int LCA(int u,int v) const {
        while(!same(u,v)){
            if(id[u]>id[v]) std::swap(u,v);
            v=par[head[v]];
        }
        return (id[u] < id[v] ? u:v);
    }
    // 任意の2頂点u,vの距離を返す　O(logN)
    int dist(int u,int v) const {
        const int w=LCA(u,v);
        return (dep[u]-dep[w])+(dep[v]-dep[w]);
    }
    // Jump on Tree　2頂点s,t及び非負整数iについて、
    // パスstにおけるi番目の頂点番号を返す　O(logN)
    int jump(int u,int v,int i) const {
        const int w=LCA(u,v);
        const int d=(dep[u]-dep[w])+(dep[v]-dep[w]);
        if(d<i) return -1;
        if(i < dep[u]-dep[w]) return LA(u,dep[u]-i);
        return LA(v,dep[v]-(d-i));
    }
};

int main(){
    cin.tie(nullptr)->ios::sync_with_stdio(false);
    int N;
    cin>>N;
    vector G(N,vector<int>());
    for(int i=0;i<N-1;i++){
        int u,v;
        cin>>u>>v;
        u--,v--;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    HeavyLightDecomposition HLD(G);
    struct node1{
        long val,len;
    };
    auto op1=[](node1 a,node1 b){ return node1(a.val+b.val,a.len+b.len); };
    auto e1=[]{ return node1(0l,0l); };
    auto mapping1=[](long f,node1 x){ return node1(x.val+x.len*f,x.len); };
    auto composition1=[](long f,long g){ return f+g; };
    auto id1=[]{ return 0l; };
    vector<node1> ini1(N,node1(0,1));
    atcoder::lazy_segtree<node1,op1,e1,long,mapping1,composition1,id1> seg(ini1);
    int Q;
    cin>>Q;
    while(Q--){
        int a,b;
        cin>>a>>b;
        a--,b--;
        while(!HLD.same(a,b)){
            HLD.normalizePair(a,b);
            const int r=HLD.heavyR(b);
            seg.apply(HLD.toSeq(r),HLD.toSeq(b)+1,1);
            b=HLD.parent(r);
        }
        HLD.normalizePair(a,b);
        seg.apply(HLD.toSeq(a),HLD.toSeq(b)+1,1);
    }
    long ans{};
    for(int i=0;i<N;i++){
        const long val=seg.get(i).val;
        ans+=val*(val+1)/2;
    }
    cout<<ans<<"\n";
}