結果

問題 No.399 動的な領主
ユーザー it_is_a_pity_
提出日時 2025-03-09 16:30:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 651 ms / 2,000 ms
コード長 5,506 bytes
コンパイル時間 5,015 ms
コンパイル使用メモリ 268,076 KB
実行使用メモリ 26,656 KB
最終ジャッジ日時 2025-03-09 16:30:38
合計ジャッジ時間 12,818 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
#define ll long long
#define rep(i,n) for(ll i=0;i<(ll)n;i++)
#define all(v) v.begin(),v.end()
const ll INF = (ll)2e18;

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

/*
HL分解(Heavy Light Decomposition)-----
    vid: 頂点のid(0-indexed)
    inv: inv[vid[v]] = v
    par: id of parent
    depth
    subsize: 部分木の大きさ
    head: head-id in the heavy-path
    next: next-id in the heavy-path
    type: the id of tree for forest

計算量----------------------------------
build()                     O(N)
lca(u,v)                    O(logN)
for_each_nodes(u,v,func)    O(f*logN)   
    頂点に関するクエリ
    fは列に対してかかる計算量
    セグ木ならf=logNなので1クエリO((logN)^2)

for_each_edges(u,v,func)    O(f*logN)
    辺クエリ


補足-----------------------------------
辺クエリの場合、(u,v)でvid[u]<vid[v]として
    seg木のvid[v]番目をweightにする
    vid[u]>vid[v]ならswap(u,v)をした方がよい

頂点クエリでもおそらく同様

列への処理を行う引数の関数funcはラムダ式などでよい
    [&](int a,int b){ans+=seg.prod(a,b+1)}
        [a,b)ではなく[a,b]であることに注意
        ansも自分で用意すること

列への処理はセグ木等を使用すること


これはけんちょんさんのライブラリ
https://drken1215.hatenablog.com/entry/2018/08/14/014800

*/

typedef vector<vector<int> > Graph;
struct HLDecomposition {
    int n;
    Graph G;
    //vidは0から始まる
    vector<int> vid, inv, par, depth, subsize, head, next, type;
    
    // construct
    HLDecomposition() { }
    HLDecomposition(const Graph &G_) :
        n((int)G_.size()), G(G_),
        vid(n, -1), inv(n), par(n), depth(n), subsize(n, 1),
        head(n), next(n, -1), type(n) { }
    void build(vector<int> roots = {0}) {
        int curtype = 0, pos = 0;
        for (auto r : roots) dfs(r), bfs(r, curtype++, pos);
    }
    void dfs(int r) {
        stack<pair<int,int> > st;
        par[r] = -1, depth[r] = 0;
        st.emplace(r, 0);
        while (!st.empty()) {
            int v = st.top().first;
            int &i = st.top().second;
            if (i < (int)G[v].size()) {
                int e = G[v][i++];
                if (e == par[v]) continue;
                par[e] = v, depth[e] = depth[v] + 1;
                st.emplace(e, 0);
            }
            else {
                st.pop();
                int maxsize = 0;
                for (auto e : G[v]) {
                    if (e == par[v]) continue;
                    subsize[v] += subsize[e];
                    if (maxsize < subsize[e]) maxsize = subsize[e], next[v] = e;
                }
            }
        }
    }
    void bfs(int r, int curtype, int &pos) {
        queue<int> que({r});
        while (!que.empty()) {
            int start = que.front(); que.pop();
            for (int v = start; v != -1; v = next[v]) {
                type[v] = curtype;
                vid[v] = pos++;
                inv[vid[v]] = v;
                head[v] = start;
                for (auto e : G[v]) if (e != par[v] && e != next[v]) que.push(e);
            }
        }
    }
    
    // node query [u, v], f([left, right])
    // 閉区間であるので、セグ木等の演算では右側を+1すること
    void for_each_nodes(int u, int v, const function<void(int,int)> &f) {
        while (true) {
            if (vid[u] > vid[v]) swap(u, v);
            f(max(vid[head[v]], vid[u]), vid[v]);
            if (head[u] != head[v]) v = par[head[v]];
            else break;
        }
    }
    
    // edge query [u, v], f([left, right])
    // 閉区間であるので、セグ木等の演算では右側を+1すること
    void for_each_edges(int u, int v, const function<void(int,int)> &f) {
        while (true) {
            if (vid[u] > vid[v]) swap(u, v);
            if (head[u] != head[v]) {
                f(vid[head[v]], vid[v]);
                v = par[head[v]];
            }
            else {
                if (u != v) f(vid[u] + 1, vid[v]);
                break;
            }
        }
    }

    // LCA
    int lca(int u, int v) {
        while (true) {
            if (vid[u] > vid[v]) swap(u, v);
            if (head[u] == head[v]) return u;
            v = par[head[v]];
        }
    }
};

struct S{
    long long value;
    int size;
};
using F = long long;
S op(S a, S b){ return {a.value+b.value, a.size+b.size}; }
S e(){ return {0, 0}; }
S mapping(F f, S x){ return {x.value + f*x.size, x.size}; }
F composition(F f, F g){ return f+g; }
F id(){ return 0; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N;
    cin >> N;
    vector<ll> u(N - 1), v(N - 1);
    vector<vector<int>> G(N);

    rep(i,N-1){
        cin >> u[i] >> v[i];
        u[i]--;
        v[i]--;
        G[u[i]].push_back(v[i]);
        G[v[i]].push_back(u[i]);
    }

    HLDecomposition HLD(G);
    HLD.build();
    vector<S> vec(N,{0, 1});
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(vec);

    ll Q;
    cin >> Q;
    ll ans = 0;

    rep(i,Q){
        ll A, B;
        cin >> A >> B;
        A--;
        B--;
        HLD.for_each_nodes(A, B, 
            [&](int a, int b){
                seg.apply(a,b+1,1);
                ans+=seg.prod(a,b+1).value; 
            }
        );
    }
    cout << ans << endl;
}
0