#726162 (C++17) No.399 動的な領主

• 問題: No.399 動的な領主
• ユーザー: Tatsuyaaaa
• 提出日時: 2021-12-24 04:19:33
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 550 ms / 2,000 ms
• コード長: 13,870 bytes
• コンパイル時間: 2,880 ms
• コンパイル使用メモリ: 228,080 KB
• 実行使用メモリ: 46,716 KB
• 最終ジャッジ日時: 2024-09-19 00:37:11
• 合計ジャッジ時間: 8,808 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	0 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	4 ms; 5,376 KB
testcase_05	AC	36 ms; 6,656 KB
testcase_06	AC	529 ms; 35,272 KB
testcase_07	AC	525 ms; 35,168 KB
testcase_08	AC	531 ms; 35,752 KB
testcase_09	AC	540 ms; 35,692 KB
testcase_10	AC	5 ms; 5,376 KB
testcase_11	AC	28 ms; 6,784 KB
testcase_12	AC	397 ms; 37,488 KB
testcase_13	AC	391 ms; 37,500 KB
testcase_14	AC	117 ms; 46,696 KB
testcase_15	AC	153 ms; 46,716 KB
testcase_16	AC	229 ms; 41,228 KB
testcase_17	AC	550 ms; 35,476 KB
testcase_18	AC	525 ms; 35,668 KB

ソースコード

#include <bits/stdc++.h>

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>


#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder {

namespace internal {

int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

}  // namespace internal

}  // namespace atcoder


namespace atcoder {

template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree {
  public:
    lazy_segtree() : lazy_segtree(0) {}
    explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

}  // namespace atcoder

using namespace std;
using namespace atcoder;
#define ll long long

struct edge {
    int from, to;
};

int N, Q;
vector<vector<edge>> G;

namespace atcoder {

template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree_hld {
  public:
    lazy_segtree_hld() : lazy_segtree_hld(0) {}
    explicit lazy_segtree_hld(int n, vector<vector<edge>> _G) : lazy_segtree_hld(std::vector<S>(n, e()), _G) {}
    explicit lazy_segtree_hld(const std::vector<S>& v, vector<vector<edge>> _G) : _n(int(v.size())) {

        // ######################################### add #########################################
        N = _n;
        G = _G;
        parent = vector<int>(N, -1);
        subtree_size = vector<int>(N);
        dfs_size(0, -1);

        depth = vector<int>(N);
        dfs_depth(0, -1);

        pre = vector<int>(N);
        A = vector<int>(N);
        HLD(0, -1, 0);
        // #######################################################################################

        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + pre[i]] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    // ######################################### add #########################################
    int N;
    vector<vector<edge>> G;
    vector<int> parent;
    vector<int> subtree_size;
    vector<int> depth;

    vector<int> pre;
    vector<int> hld_vec;
    // lowest index in heavy component
    vector<int> A;

    void dfs_size(int idx, int par) {
        parent[idx] = par;
        subtree_size[idx] = 1;
        for (auto ee : G[idx]) {
            if (ee.to == par) continue;
            dfs_size(ee.to, idx);
            subtree_size[idx] += subtree_size[ee.to];
        }
    }

    void dfs_depth(int idx, int par) {
        depth[idx] = ((par==-1)?0:(depth[par]+1));
        for (auto ee : G[idx]) {
            if (ee.to == par) continue;
            dfs_depth(ee.to, idx);
        }
    }

    void HLD(int idx, int par, int a) {
        pre[idx] = hld_vec.size();
        hld_vec.push_back(idx);
        A[idx] = a;

        int max_size = 0;
        int max_idx = -1;
        for (auto ee : G[idx]) {
            if (ee.to == par) continue;
            if (subtree_size[ee.to] > max_size) {
                max_size = subtree_size[ee.to];
                max_idx = ee.to;
            }
        }
        if (max_idx == -1) return;
        HLD(max_idx, idx, a);

        for (auto ee : G[idx]) {
            if (ee.to == par) continue;
            if (ee.to != max_idx) HLD(ee.to, idx, ee.to);
        }
    }
    // #######################################################################################

    void set(int p, S x) {
        // ############ change ############
        p = pre[p];
        // ################################
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        // ############ change ############
        p = pre[p];
        // ################################
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    // ######################################### add #########################################
    // path query [l, r]
    // S prod_path(int l, int r) {
    //     S s_l = e();
    //     S s_r = e();
    //     while (A[l] != A[r]) {
    //         if (depth[A[l]] <= depth[A[r]]) {
    //             s_r = op(prod(pre[A[r]], pre[r]+1), s_r);
    //             r = parent[A[r]];
    //         } else {
    //             s_l = op(prod(pre[A[l]], pre[l]+1), s_l);
    //             l = parent[A[l]];
    //         }
    //     }
    //     if (pre[l] <= pre[r]) {
    //         s_l.reverse();
    //         return op(op(s_l, prod(pre[l], pre[r]+1)), s_r);
    //     } else {
    //         assert(pre[r] < pre[l]);
    //         s_r.reverse();
    //         return op(op(s_r, prod(pre[r], pre[l]+1)), s_l);
    //     }
    // }
    S prod_path(int l, int r) {
        S ret = e();
        while (A[l] != A[r]) {
            if (depth[A[l]] <= depth[A[r]]) {
                ret = op(ret, prod(pre[A[r]], pre[r]+1));
                r = parent[A[r]];
            } else {
                ret = op(ret, prod(pre[A[l]], pre[l]+1));
                l = parent[A[l]];
            }
        }
        ret = op(ret, prod(min(pre[l], pre[r]), max(pre[l], pre[r])+1));
        return ret;
    }

    S prod_subtree(int p) {
        return prod(pre[p], pre[p]+subtree_size[p]);
    }
    // #######################################################################################

    S all_prod() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    // ######################################### add #########################################
    // apply path query [l, r]
    void apply_path(int l, int r, F f) {
        while (A[l] != A[r]) {
            if (depth[A[l]] <= depth[A[r]]) {
                apply(pre[A[r]], pre[r]+1, f);
                r = parent[A[r]];
            } else {
                apply(pre[A[l]], pre[l]+1, f);
                l = parent[A[l]];
            }
        }
        apply(min(pre[l], pre[r]), max(pre[l], pre[r])+1, f);
    }

    void apply_subtree(int p, F f) {
        apply(pre[p], pre[p]+subtree_size[p], f);
    }
    // #######################################################################################

  private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

}  // namespace atcoder

struct S {
    ll sum_val, sz;
};

S op(S a, S b) {
    return S{a.sum_val+b.sum_val, a.sz+b.sz};
}
S e() {
    return S{0, 0};
}

using F = long long;

S mapping(F f, S a) {
    return S{a.sum_val+f*a.sz, a.sz};
}

F composition(F a, F b) {
    return a+b;
}

F id() {
    return 0LL;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    G = vector<vector<edge>>(N, vector<edge>());
    for (int i=0;i<N-1;i++) {
        int u, v;
        cin >> u >> v;
        u--;v--;
        G[u].push_back(edge{u, v});
        G[v].push_back(edge{v, u});
    }
    cin >> Q;
    lazy_segtree_hld<S, op, e, F, mapping, composition, id> seg(N, G);
    for (int i=0;i<N;i++) seg.set(i, S{0, 1});

    ll ans = 0LL;
    for (int i=0;i<Q;i++) {
        int A, B;
        cin >> A >> B;
        A--;B--;
        seg.apply_path(A, B, 1LL);
        ans += seg.prod_path(A, B).sum_val;
    }
    cout << ans << "\n";
    return 0;
}