#1112191 (C++23) No.1817 Reversed Edges

提出ソース
結果

問題	No.1817 Reversed Edges
ユーザー	nonon
提出日時	2025-08-14 21:22:39
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	186 ms / 2,000 ms
コード長	17,203 bytes
コンパイル時間	4,660 ms
コンパイル使用メモリ	309,888 KB
実行使用メモリ	53,836 KB
最終ジャッジ日時	2025-08-14 21:22:49
合計ジャッジ時間	9,797 ms
ジャッジサーバーID （参考情報）	judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 2
other	AC * 23
権限があれば一括ダウンロードができます
ソースコード

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

using ll = long long;

bool chmin(auto &a, auto b) { return a > b ? a = b, true : false; }
bool chmax(auto &a, auto b) { return a < b ? a = b, true : false; }

template<typename ActMonoid>
struct lazy_segtree {
    using M = ActMonoid;
    using S = typename M::S;
    using F = typename M::F;
    lazy_segtree() : lazy_segtree(0) {}
    lazy_segtree(int _n) : lazy_segtree(vector<S>(_n, M::e())) {}
    lazy_segtree(const vector<S> &v) { init(v); }
    void set(const vector<S> &v) { init(v); }
    void set(int p, const S &x) {
        assert(0 <= p && p < n);
        p += sz;
        inner_push(p);
        d[p] = x;
        inner_update(p);
    }
    void apply(int p, const F &f) {
        assert(0 <= p && p < n);
        p += sz;
        inner_push(p);
        d[p] = M::map(f, d[p]);
        inner_update(p);
    }
    void apply(int l, int r, const F &f) {
        assert(0 <= l && l <=r && r <= n);
        l += sz;
        r += sz;
        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);
        }
    }
    S get(int p) {
        assert(0 <= p && p < n);
        p += sz;
        inner_push(p);
        return d[p];
    }
    S prod(int l, int r) {
        assert(0 <= l && l <=r && r <= n);
        l += sz;
        r += sz;
        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 pl = M::e(), pr = M::e();
        while (l < r) {
            if (l & 1) pl = M::op(pl, d[l++]);
            if (r & 1) pr = M::op(d[--r], pr);
            l >>= 1;
            r >>= 1;
        }
        return M::op(pl, pr);
    }
    S all_prod() const { return d[1]; }
    template<typename C>
    int max_right(int l, const C &check) {
        assert(0 <= l && l <= n);
        assert(check(M::e()));
        if (l == n) return l;
        l += sz;
        inner_push(l);
        S p = M::e();
        do {
            while (!(l & 1)) l >>= 1;
            S np = M::op(p, d[l]);
            if (!check(np)) {
                while (l < sz) {
                    l <<= 1;
                    np = M::op(p, d[l]);
                    if (check(np)) {
                        p = np;
                        l++;
                    }
                }
                return l - sz;
            }
            p = np;
            l++;
        } while ((l & -l) != l);
        return n;
    }
    template<typename C>
    int max_right(const C &check) {
        return max_right(0, check);
    }
    template<typename C>
    int min_left(int r, int l, const C &check) {
        assert(0 <= r && r <= n);
        assert(check(M::e()));
        if (r == 0) return l;
        r += sz;
        inner_push(r - 1);
        S p = M::e();
        do {
            r--;
            while (r > 1 && r & 1) r >>= 1;
            S np = M::op(d[r], p);
            if (!check(np)) {
                while (r < sz) {
                    push(r);
                    (r <<= 1)++;
                    np = M::op(d[r], p);
                    if (check(np)) {
                        p = np;
                        r--;
                    }
                }
                return r + 1 - sz;
            }
            p = np;
        } while ((r & -r) != r);
        return 0;
    }
    template<typename C>
    int min_left(const C &check) {
        return min_left(n, check);
    }
private:
    int n, log, sz;
    vector<S> d;
    vector<F> lz;
    void init(const vector<S> &v) {
        n = v.size();
        log = 1;
        while ((1 << log) < n) log++;
        sz = 1 << log;
        d = vector<S>(2 * sz, M::e());
        lz = vector<F>(sz, M::id());
        for (int i = 0; i < n; i++) d[i + sz] = v[i];
        for (int i = sz - 1; i >= 1; i--) update(i);
    }
    void update(int p) {
        d[p] = M::op(d[2 * p], d[2 * p + 1]);
    }
    void all_apply(int p, const F &f) {
        d[p] = M::map(f, d[p]);
        if (p < sz) lz[p] = M::comp(f, lz[p]);
    }
    void push(int p) {
        all_apply(2 * p, lz[p]);
        all_apply(2 * p + 1, lz[p]);
        lz[p] = M::id();
    }
    void inner_update(int p) {
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void inner_push(int p) {
        for (int i = log; i >= 1; i--) push(p >> i);
    }
};

template<typename SegTree, bool edge, bool commutative>
struct heavy_light_decomposition {
    using M = typename SegTree::M;
    using S = typename M::S;
    heavy_light_decomposition() = default;
    heavy_light_decomposition(int _n, int _r = 0) : n(_n), r(_r), id(0), built(false) {
        edges.reserve(n - 1);
        if (n <= 1) build();
    }
    void add_edge(int u, int v, const S &w = M::e()) {
        assert(!built);
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        assert(u != v);
        edges.emplace_back(u, v, w);
        if (ssize(edges) + 1 == n) build();
    }
    int lca(int u, int v) {
        assert(built);
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        while (true) {
            if (in[u] > in[v]) swap(u, v);
            if (head[u] == head[v]) return u;
            v = par[head[v]];
        }
        return -1;
    }
    void set(int u, const S &w) {
        assert(built);
        assert(0 <= u && u < n);
        seg.set(idx(u), w);
    }
    void set(int u, int v, const S &w) {
        assert(built);
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        assert(u != v);
        seg.set(idx(u, v), w);
    }
    template<typename F>
    void apply(int u, int v, const F &f) {
        assert(built);
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        for (auto [l, r] : path_decompose(u, v)) {
            if (l > r) swap(l, r);
            seg.apply(l, r, f);
        }
    }
    template<typename F>
    void subtree_apply(int u, const F &f) {
        assert(built);
        assert(0 <= u && u < n);
        seg.apply(in[u] + edge, out[u], f);
    }
    S get(int u) {
        assert(built);
        assert(0 <= u && u < n);
        return seg.get(idx(u));
    }
    S get(int u, int v) {
        assert(built);
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        assert(u != v);
        return seg.get(idx(u, v));
    }
    S prod(int u, int v) {
        assert(built);
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        S p = M::e();
        for (auto [l, r] : path_decompose(u, v)) {
            p = M::op(p, inner_prod(l, r));
        }
        return p;
    }
    S subtree_prod(int u) {
        assert(built);
        assert(0 <= u && u < n);
        return seg.prod(in[u] + edge, out[u]);
    }
    template<typename C>
    int binary_search(int u, int v, const C &check) {
        assert(built);
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        S p = M::e();
        for (auto [l, r] : path_decompose(u, v)) {
            S np = M::op(p, inner_prod(l, r));
            if (l < r) {
                if (!check(np)) {
                    return check(M::op(p, seg.get(l))) ? inv[
                        (commutative ? seg.max_right(l, [&](const S &x) {
                            return check(M::op(p, x));
                        }) : seg.max_right(l, false, [&](const S &x) {
                            return check(M::op(p, x));
                        })) - 1
                    ] : u;
                }
                p = np;
                u = inv[r - 1];
            } else {
                swap(l, r);
                if (!check(np)) {
                    return check(M::op(p, seg.get(r - 1))) ? inv[
                        commutative ? seg.min_left(r, [&](const S &x) {
                            return check(M::op(p, x));
                        }) : seg.min_left(r, true, [&](const S &x) {
                            return check(M::op(p, x));
                        })
                    ] : u;
                }
                p = np;
                u = inv[l];
            }
        }
        return v;
    }
private:
    int n, r, id;
    bool built;
    SegTree seg;
    vector<vector<int>> g;
    vector<int> sub, depth, par, in, out, inv, head, heavy;
    vector<tuple<int, int, S>> edges;
    int idx(int u) const {
        assert(built);
        return in[u];
    }
    int idx(int u, int v) const {
        assert(built);
        return max(in[u], in[v]);
    }
    S inner_prod(int l, int r) {
        if (commutative && l > r) swap(l, r);
        return seg.prod(l, r);
    }
    void dfs(int u, int p) {
        par[u] = p;
        sub[u] = 1;
        int sub_max = 0;
        for (int v : g[u]) {
            if (v != p) {
                dfs(v, u);
                sub[u] += sub[v];
                if (sub[v] > sub_max) {
                    sub_max = sub[v];
                    heavy[u] = v;
                }
            }
        }
    }
    void decompose(int u, int h) {
        head[u] = h;
        in[u] = id++;
        inv[in[u]] = u;
        if (heavy[u] != -1) decompose(heavy[u], h);
        for (int v : g[u]) {
            if (v != par[u] && v != heavy[u]) {
                decompose(v, v);
            }
        }
        out[u] = id;
    }
    void build() {
        g = vector<vector<int>>(n);
        sub = depth = in = inv = out = head = vector<int>(n);
        par = heavy = vector<int>(n, -1);
        for (const auto &[u, v, _] : edges) {
            g[u].emplace_back(v);
            g[v].emplace_back(u);
        }
        dfs(r, r);
        decompose(r, r);
        built = true;
        if (edge) {
            vector<S> a(n, M::e());
            for (const auto &[u, v, w] : edges) {
                a[idx(u, v)] = w;
            }
            seg = SegTree(a);
        } else {
            seg = SegTree(n);
        }
    }
    vector<pair<int, int>> path_decompose(int u, int v) const {
        assert(built);
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        int hu = head[u], hv = head[v];
        vector<pair<int, int>> resl, resr;
        bool flip = true;
        while (hu != hv) {
            if (in[hu] > in[hv]) {
                flip = !flip;
                swap(u, v);
                swap(hu, hv);
                swap(resl, resr);
            }
            resl.emplace_back(in[hv], in[v] + 1);
            v = par[hv];
            hu = head[u];
            hv = head[v];
        }
        if (in[u] > in[v]) {
            flip = !flip;
            swap(u, v);
            swap(resl, resr);
        }
        resl.emplace_back(in[u] + edge, in[v] + 1);
        if (flip) swap(resl, resr);
        reverse(resr.begin(), resr.end());
        vector<pair<int, int>> res;
        for (auto [l, r] : resl) res.emplace_back(r, l);
        for (auto [l, r] : resr) res.emplace_back(l, r);
        return res;
    }
};
#include <bit>

template<typename Monoid>
struct sparse_table {
    using M = Monoid;
    using S = typename M::S;
    sparse_table() = default;
    sparse_table(const vector<S> &v) : n(v.size()), b(0), d(1, v) { build(); }
    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <=n);
        if (l == r) return M::e();
        int i = bit_width(unsigned(r - l)) - 1;
        return M::op(d[i][l], d[i][r - (1 << i)]);
    }
private:
    int n, b, e;
    vector<vector<S>> d;
    void build() {
        b = bit_width(unsigned(n));
        d.resize(b, vector<S>(n, M::e()));
        for (int i = 1; i < b; i++) {
            for (int j = 0; j + (1 << i) <=n; j++) {
                d[i][j] = M::op(d[i - 1][j], d[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
};

// https://judge.yosupo.jp/submission/200540
// 小さい部分は愚直が速いらしい(?)
template<typename Monoid>
struct static_rmq {
    using M = Monoid;
    using S = typename M::S;
    static_rmq() = default;
    static_rmq(const vector<S> &_v) : n(_v.size()), v(_v), pref(_v), suf(_v) { build(); }
    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) return M::e();
        r--;
        int bl = l >> log, br = r >> log;
        if (bl < br) {
            return M::op(M::op(pref[r], suf[l]), st.prod(bl + 1, br));
        }
        S p = M::e();
        for (int i = l; i <= r; i++) p = M::op(p, v[i]);
        return p;
    }
private:
    int n;
    static constexpr int log = 4, mask = 15;
    vector<S> v, pref, suf;
    sparse_table<M> st;
    void build() {
        for (int i = 1; i < n; i++) {
            if (i & mask) pref[i] = min(pref[i - 1], v[i]);
        }
        for (int i = n - 1; i > 0; i--) {
            if (i & mask) suf[i - 1] = min(suf[i], v[i - 1]);
        }
        st = sparse_table<M>([&]{
            vector<S> a(n >> log);
            for (int i = 0; i < (n >> log); i++) {
                a[i] = suf[i << log];
            }
            return a;
        }());
    }
};

struct static_tree {
    static_tree() = default;
    static_tree(int _n, int r = 0) : n(_n), e(0), root(r), g(_n), built(false) {
        if (n <= 1) build();
    }
    void add_edge(int u, int v) {
        assert(!built);
        assert(e < n - 1);
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        g[u].push_back(v);
        g[v].push_back(u);
        if (++e == n - 1) build();
    }
    vector<int> &operator[](int u) {
        return g[u];
    }
    int depth(int u) const {
        assert(built);
        return d[u];
    }
    int lca(int u, int v, int r = -1) const {
        assert(built);
        if (r == -1) {
            auto [l, r] = minmax({in[u], in[v]});
            return st.prod(l, r + 1).second;
        }
        return lca(u, v) ^ lca(v, r) ^ lca(r, u);
    }
    int dist(int u, int v) const {
        assert(built);
        int w = lca(u, v);
        return d[u] + d[v] - 2 * d[w];
    }
    int jump(int u, int v, int k) const {
        assert(built);
        int w = lca(u, v);
        if (d[u] + d[v] - 2 * d[w] < k) return -1;
        if (d[u] - d[w] < k) {
            swap(u, v);
            k = d[u] + d[v] - 2 * d[w] - k;
        }
        k = d[u] - k;
        return *prev(upper_bound(list[k].begin(), list[k].end(), u, [&](int i, int j) {
            return in[i] < in[j];
        }));
    }
private:
    struct Monoid {
        using S = pair<int, int>;
        static S op(S a, S b) {
            return min(a, b);
        }
        static S e() {
            return make_pair(1 << 30, -1);
        }
    };
    int n, e, root;
    vector<vector<int>> g, list;
    bool built;
    vector<int> d, ord, in;
    static_rmq<Monoid> st;
    void dfs(int u, int p) {
        ord.push_back(u);
        list[d[u]].push_back(u);
        for (int v : g[u]) {
            if (v != p) {
                d[v] = d[u] + 1;
                dfs(v, u);
                ord.push_back(u);
            }
        }
    }
    void build() {
        if (built) return;
        d = vector<int>(n, 0);
        ord.reserve(2 * n);
        list = vector<vector<int>>(n);
        dfs(root, root);
        in = vector<int>(n, -1);
        st = static_rmq<Monoid>([&]{
            vector<pair<int, int>> a(ord.size());
            for (int i = 0; i < ssize(ord); i++) {
                int u = ord[i];
                if (in[u] == -1) in[u] = i;
                a[i] = make_pair(d[u], u);
            }
            return a;
        }());
        built = true;
    }
};

struct Monoid {
    using S = int;
    static S op(S a, S b) {
        return a + b;
    }
    static S e() {
        return 0;
    }
    using F = int;
    static F comp(F f, F g) {
        return f + g;
    }
    static F id() {
        return 0;
    }
    static S map(F f, S x) {
        return f + x;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    static_tree G(N);
    heavy_light_decomposition<lazy_segtree<Monoid>, false, true> HLD(N);
    vector<int> U(N - 1), V(N - 1);
    for (int i = 0, u, v; i < N - 1; i++) {
        cin >> u >> v;
        u--, v--;
        G.add_edge(u, v);
        HLD.add_edge(u, v);
        U[i] = u, V[i] = v;
    }
    auto apply = [&] (int u, int v) -> void {
        if (G.lca(u, v) == v) {
            // cout << "apply: " << 0 << ' ' << 1 << endl;
            // cout << "apply: " << u << ' ' << -1 << endl;
            HLD.subtree_apply(0, 1);
            HLD.subtree_apply(u, -1);
        } else {
            // cout << "apply: " << v << ' ' << 1 << endl;
            HLD.subtree_apply(v, 1);
        }
    };
    for (int i = 0; i < N - 1; i++) {
        int u = U[i], v = V[i];
        if (u > v) swap(u, v);
        apply(u, v);
    }
    for (int i = 0; i < N; i++) {
        cout << HLD.get(i) << '\n';
    }
}
yukicoder

結果

ソースコード
