結果

問題 No.399 動的な領主
ユーザー yano2xyyano2xy
提出日時 2024-02-11 23:53:32
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 382 ms / 2,000 ms
コード長 5,717 bytes
コンパイル時間 4,416 ms
コンパイル使用メモリ 280,124 KB
実行使用メモリ 44,312 KB
最終ジャッジ日時 2024-09-28 17:46:22
合計ジャッジ時間 9,513 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 1 ms
6,816 KB
testcase_04 AC 3 ms
6,816 KB
testcase_05 AC 25 ms
6,820 KB
testcase_06 AC 372 ms
37,712 KB
testcase_07 AC 366 ms
37,592 KB
testcase_08 AC 374 ms
37,408 KB
testcase_09 AC 373 ms
37,392 KB
testcase_10 AC 4 ms
6,816 KB
testcase_11 AC 21 ms
6,820 KB
testcase_12 AC 267 ms
37,452 KB
testcase_13 AC 264 ms
37,388 KB
testcase_14 AC 104 ms
44,312 KB
testcase_15 AC 130 ms
43,892 KB
testcase_16 AC 182 ms
40,900 KB
testcase_17 AC 382 ms
37,644 KB
testcase_18 AC 371 ms
37,428 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
// clang-format off
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); i++)
template <class T,class S> inline bool chmax(T &a,const S &b) {return (a<b? a=b,1:0);}
template <class T,class S> inline bool chmin(T &a,const S &b) {return (a>b? a=b,1:0);}
using ll = long long;
// clang-format on
#ifdef LOCAL
#include <util/debug_print.hpp>
#else
#define debug(...) static_cast<void>(0)
#endif

/* Edge */
template <typename T = ll> struct Edge {
    int id;
    int from;
    int to;
    T cost;
    bool operator<(const Edge &other) const { return cost < other.cost; }
    bool operator>(const Edge &other) const { return cost > other.cost; }
};

/* Graph */
template <typename T = ll> struct Graph {
    int _n;
    vector<vector<Edge<T>>> _graph;
    const T INF = numeric_limits<T>::max() / 2;
    vector<Edge<T>> _edges;  // i番目に追加された辺をもつ

    Graph(int n) : _n(n) { _graph.resize(_n); }
    vector<Edge<T>> &operator[](int i) { return _graph[i]; }
    int size() { return _n; }

    /* 頂点 u v 間に重さ cost の双方向の辺を張る */
    void add_edge(int u, int v, T cost) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int id = (int)_edges.size();
        _graph[u].push_back({id, u, v, cost});
        _graph[v].push_back({id, v, u, cost});
        _edges.push_back({id, u, v, cost});
    }

    /* 頂点 from から 頂点 to に cost の有向辺を張る */
    void add_edge_directed(int from, int to, T cost) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        int id = (int)_edges.size();
        _graph[from].push_back({(int)_edges.size(), from, to, cost});
        _edges.push_back({id, from, to, cost});
    }

    /* 頂点 u v 間に重さ 1 の双方向の辺を張る */
    void add_edge(int u, int v) { add_edge(u, v, 1); }

    /* 頂点 from から 頂点 to に重さ 1 の有向辺を張る */
    void add_edge_directed(int from, int to) { add_edge_directed(from, to, 1); }

    /* i番目の辺を返す */
    Edge<T> getEdge(int i) {
        assert(0 <= i && i < (int)_edges.size());
        return _edges[i];
    }
};

template <typename T> struct HLD {
   private:
    void dfs_sz(int v) {
        auto &es = G[v];
        if (~par[v]) es.erase(find(es.begin(), es.end(), par[v]));
        for (int &u : es) {
            par[u] = v;
            dfs_sz(u);
            sub[v] += sub[u];
            if (sub[u] > sub[es[0]]) swap(u, es[0]);
        }
    }
    void dfs_hld(int v, int &pos) {
        vid[v] = pos++;
        inv[vid[v]] = v;
        for (int u : G[v]) {
            if (u == par[v]) continue;
            nxt[u] = (u == G[v][0] ? nxt[v] : u);
            dfs_hld(u, pos);
        }
    }

   public:
    int n;
    vector<vector<int>> G;
    vector<int> vid, nxt, sub, par, inv;
    HLD(Graph<T> _g, int root = 0) : n((int)_g.size()), vid(n, -1), nxt(n), sub(n, 1), par(n, -1), inv(n) {
        G.resize(n);
        for (int pos = 0; pos < n; pos++) {
            for (auto e : _g._graph[pos]) {
                G[pos].push_back(e.to);
            }
        }
        dfs_sz(root);
        nxt[root] = root;
        int pos = 0;
        dfs_hld(root, pos);
    }
    int lca(int u, int v) {
        while (true) {
            if (vid[u] > vid[v]) swap(u, v);
            if (nxt[u] == nxt[v]) return u;
            v = par[nxt[v]];
        }
    }
    /* f の引数は半開区間 [l, r)*/
    void query_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[nxt[v]], vid[u]), vid[v] + 1);
            if (nxt[u] != nxt[v]) v = par[nxt[v]];
            else break;
        }
    }
    /* f の引数は半開区間 [l, r) */
    void query_each_edges(int u, int v, const function<void(int, int)> &f) {
        while (true) {
            if (vid[u] > vid[v]) swap(u, v);
            if (nxt[u] != nxt[v]) {
                f(vid[nxt[v]], vid[v] + 1);
                v = par[nxt[v]];
            } else {
                if (u != v) f(vid[u] + 1, vid[v] + 1);
                break;
            }
        }
    }
};
/* HLD (Heavy-Light Decomposition)
    vid: 頂点->id
    inv: id->頂点
    nxt: HL分解後の連結成分内の最も小さい頂点
    par: 頂点の親

    query_for_nodes(u, v, f): パス上の各頂点に対するクエリに対応する.
    query_for_edges(u, v, f): パス上の全ての辺に対するクエリに対応する.
    f = [&](int l, int r) { *** } : 半開区間[l, r) に対する処理

       1
     / |
    2  3  例) パス[1,2]の情報は、頂点2に持たせる
*/

//
// 区間加算 & 区間和取得
//
struct S {
    ll value;
    int size;
};
using F = ll;
S op(S a, S b) {
    return {a.value + b.value, a.size + b.size};
}
S e() {
    return {0, 1};
}
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() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    Graph G(n);
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(n);
    rep(i, n - 1) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        G.add_edge(u, v);
    }
    HLD hld(G);

    int Q;
    cin >> Q;
    while (Q--) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        hld.query_each_nodes(a, b, [&](int l, int r) { seg.apply(l, r, 1); });
    }

    ll ans = 0;
    rep(i, n) {
        ll x = seg.get(i).value;
        ans += x * (x + 1) / 2;
    }
    cout << ans << '\n';

    return 0;
}
0