結果

問題 No.399 動的な領主
ユーザー kcvlexkcvlex
提出日時 2019-12-06 21:01:59
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 869 ms / 2,000 ms
コード長 7,992 bytes
コンパイル時間 2,269 ms
コンパイル使用メモリ 193,760 KB
実行使用メモリ 59,564 KB
最終ジャッジ日時 2023-08-25 12:36:42
合計ジャッジ時間 10,495 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 4 ms
4,380 KB
testcase_05 AC 52 ms
4,640 KB
testcase_06 AC 854 ms
18,068 KB
testcase_07 AC 837 ms
18,316 KB
testcase_08 AC 822 ms
18,332 KB
testcase_09 AC 832 ms
18,300 KB
testcase_10 AC 6 ms
4,376 KB
testcase_11 AC 37 ms
4,616 KB
testcase_12 AC 550 ms
18,320 KB
testcase_13 AC 527 ms
18,300 KB
testcase_14 AC 133 ms
59,564 KB
testcase_15 AC 274 ms
59,504 KB
testcase_16 AC 400 ms
39,304 KB
testcase_17 AC 869 ms
18,148 KB
testcase_18 AC 847 ms
18,320 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()

template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
using ll = int64_t;
using ull = uint64_t;
using PLL = pair<ll, ll>;

template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return max(low, min(high, t)); }
template <typename T> void chclamp(T &t, const T &low, const T &high) { t = clamp(t, low, high); }

namespace init__ {

struct InitIO {
    InitIO() {
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        cout << fixed << setprecision(30);
    }
} init_io;

}

// #include "lazysegmenttree.cpp"

template <typename T, typename L> struct LazySegmentTree {
  using Merge = function<T(T, T)>;
  using Apply = function<T(T, L)>;
  using Update = function<L(L, L)>;
  using GenLazy = function<L(ssize_t, ssize_t, L)>;
  using Propagate = function<L(L)>;

  ssize_t upper;
  T init_node;
  L init_lazy;
  V<T> node;
  V<L> lazy;
  V<bool> lazyf;

  Merge merge;
  Apply apply;
  Update update;
  GenLazy gen_lazy;
  Propagate prop;

public:
  LazySegmentTree(
      const V<T> &init_v, T init_node, L init_lazy, Merge merge, Apply apply,
      Update update, GenLazy gen_lazy, Propagate prop = [](L l) { return l; })
      : init_node(init_node), init_lazy(init_lazy), merge(merge), apply(apply),
        update(update), gen_lazy(gen_lazy), prop(prop) {
    {
      upper = 1;
      while (upper < init_v.size())
        upper *= 2;
    }
    node.resize(2 * upper - 1, init_node);
    lazy.resize(2 * upper - 1, init_lazy);
    lazyf.resize(2 * upper - 1, false);
    for (ll i = 0; i < init_v.size(); i++)
      node[i + upper - 1] = init_v[i];
    for (ll i = upper - 2; 0 <= i; i--) {
      ll c0, c1;
      tie(c0, c1) = get_child_idx(i);
      node[i] = merge(node[c0], node[c1]);
    }
  }

  PLL get_child_idx(ll pos) { return PLL(2 * pos + 1, 2 * pos + 2); }

  void push(ll pos, ll nl, ll nr) {
    if (!lazyf[pos])
      return;
    node[pos] = apply(node[pos], lazy[pos]);

    if (nr - nl > 1) {
      ll cidx[2];
      tie(cidx[0], cidx[1]) = get_child_idx(pos);
      for (ll i = 0; i <= 1; i++) {
        lazy[cidx[i]] = update(lazy[cidx[i]], prop(lazy[pos]));
        lazyf[cidx[i]] = true;
      }
    }

    lazyf[pos] = false;
    lazy[pos] = init_lazy;
  }

  T update_query(ll ql, ll qr, L val, ll pos, ll nl, ll nr) {
    push(pos, nl, nr);
    if (qr <= nl || nr <= ql)
      return init_node;
    if (ql <= nl && nr <= qr) {
      lazy[pos] = gen_lazy(nl, nr, val);
      lazyf[pos] = true;
      push(pos, nl, nr);
      return node[pos];
    } else {
      ll mid = (nl + nr) / 2;
      ll c0, c1;
      tie(c0, c1) = get_child_idx(pos);
      auto lv = update_query(ql, qr, val, c0, nl, mid);
      auto rv = update_query(ql, qr, val, c1, mid, nr);
      return node[pos] = merge(node[c0], node[c1]);
    }
  }

  T update_query(ll ql, ll qr, L val) {
    return update_query(ql, qr, val, 0, 0, upper);
  }

  T get_query(ll ql, ll qr, ll pos, ll nl, ll nr) {
    push(pos, nl, nr);

    if (nr <= ql || qr <= nl)
      return init_node;
    if (ql <= nl && nr <= qr)
      return node[pos];

    ll mid = (nl + nr) / 2;
    ll c0, c1;
    tie(c0, c1) = get_child_idx(pos);
    auto lv = get_query(ql, qr, c0, nl, mid);
    auto rv = get_query(ql, qr, c1, mid, nr);
    return merge(lv, rv);
  }

  T get_query(ll ql, ll qr) { return get_query(ql, qr, 0, 0, upper); }
};

struct HLD {
    V<ll> p_node, head_node, hld_id, heavy , tree_size;
    HLD(const VV<ll> &edges) : p_node(edges.size()), head_node(edges.size()),
                               hld_id(edges.size()), heavy(edges.size(), -1), 
                               tree_size(edges.size())
    {
        calc_size(0, -1, edges);
        ll id = 0;
        calc_id(0, -1, edges, id);
    }

    ll calc_size(ll cur, ll pre, const VV<ll> &edges) {
        ll ret = 1;
        p_node[cur] = pre;
        for(ll nxt : edges[cur]) if(nxt != pre) {
            ret += calc_size(nxt, cur, edges);
            if(heavy[cur] == -1 || 
               tree_size[heavy[cur]] < tree_size[nxt]) {
                heavy[cur] = nxt;
            }
        }
        return tree_size[cur] = ret;
    }

    void calc_id(ll cur, ll pre, const VV<ll> &edges, ll &id) {
        if(cur == -1) return;
        hld_id[cur] = id++;
        if(pre == -1) head_node[cur] = cur;
        else head_node[cur] = (heavy[pre] == cur ? head_node[pre] : cur);
        if(cur != heavy[cur]) calc_id(heavy[cur], cur, edges, id);
        for(ll nxt : edges[cur]) {
            if(nxt == pre || nxt == heavy[cur]) continue;
            calc_id(nxt, cur, edges, id);
        }
    }

    ll head_id(ll node) { return hld_id[head_node[node]]; }

    ll lca(ll n1, ll n2) {
        while(true) {
            if(hld_id[n2] < hld_id[n1]) swap(n1, n2);
            if(head_node[n1] == head_node[n2]) break;
            n2 = p_node[head_node[n2]];
        }
        return n1;
    }

    // calc's arg is [l, r)
    template <typename T>
    T query(ll n1, ll n2, function<T(ll, ll)> calc, 
            T id_ele, function<T(T, T)> merge) 
    {
        T lval = id_ele, rval = id_ele;
        T res = id_ele;
        while(true) {
            ll id1 = hld_id[n1];
            ll id2 = hld_id[n2];
            if(head_node[n1] != head_node[n2]) {
                if(id1 < id2) {
                    auto tmp = calc(head_id(n2), id2 + 1);
                    rval = merge(tmp, rval);
                    n2 = p_node[head_node[n2]];
                } else {
                    auto tmp = calc(head_id(n1), id1 + 1);
                    lval = merge(lval, tmp);
                    n1 = p_node[head_node[n1]];
                }
            } else {
                if(id2 < id1) swap(id1, id2);
                res = calc(id1, id2 + 1);
                res = merge(lval, merge(res, rval));
                break;
            }
        }
        return res;
    }

    void query(ll n1, ll n2, function<void(ll, ll)> update) {
        ll identity = 0;
        auto merge = [&](ll a, ll b) { return 0; };
        auto wrapper_calc = [&](ll a, ll b) { update(a, b); return 0; };
        query<ll>(n1, n2, wrapper_calc, identity, merge);
    }
};

int main() {
    ll N;
    cin >> N;
    VV<ll> edges(N);
    for(ll i = 1; i < N; i++) {
        ll a, b;
        cin >> a >> b;
        a--; b--;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
 
    HLD hld(edges);
    LazySegmentTree<ll, ll> lst(V<ll>(N, 1), 0, 0,
                                [](ll a, ll b) { return a + b; },
                                [](ll a, ll b) { return a + b; },
                                [](ll a, ll b) { return a + b; },
                                [](ssize_t l, ssize_t r, ll v) { return (r - l) * v; },
                                [](ll v) { return v / 2; });
    
    auto merge = [&](ll a, ll b) { return a + b; };
    auto update = [&](ll a, ll b) { lst.update_query(a, b, 1); };
    auto calc_tax = [&](ll a, ll b) { return lst.get_query(a, b); };

    ll Q;
    cin >> Q;
    ll ans = 0;
    while(Q--) {
        ll u, v;
        cin >> u >> v;
        u--; v--;
        ans += hld.query<ll>(u, v, calc_tax, 0, merge);
        hld.query(u, v, update);
    }

    cout << ans << endl;
    return 0;
}
0