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

提出ソース
結果

問題	No.399 動的な領主
ユーザー	myun-plusplus
提出日時	2020-12-15 17:35:53
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	12,679 bytes
コンパイル時間	2,430 ms
コンパイル使用メモリ	213,660 KB
実行使用メモリ	20,024 KB
最終ジャッジ日時	2023-10-20 06:10:30
合計ジャッジ時間	9,537 ms
ジャッジサーバーID （参考情報）	judge13 / judge11
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 8,696 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	2 ms 4,348 KB
testcase_03	AC	2 ms 4,348 KB
testcase_04	AC	3 ms 4,348 KB
testcase_05	AC	23 ms 4,348 KB
testcase_06	AC	335 ms 13,436 KB
testcase_07	AC	332 ms 13,436 KB
testcase_08	AC	327 ms 13,436 KB
testcase_09	AC	330 ms 13,436 KB
testcase_10	AC	4 ms 4,348 KB
testcase_11	AC	14 ms 4,348 KB
testcase_12	AC	192 ms 13,964 KB
testcase_13	AC	179 ms 13,964 KB
testcase_14	AC	62 ms 17,660 KB
testcase_15	AC	140 ms 17,660 KB
testcase_16	TLE	-
testcase_17	--	-
testcase_18	--	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
//#define ATCODER_EX_DEBUG

#include <type_traits>
#include <utility>
#include <vector>
#include <cstddef>

#include <iostream>

namespace atcoder_ex {
    
template<bool Is_Evertable = false, class S = std::nullptr_t, S(*op)(S, S) = nullptr, S(*e)() = nullptr,
    class F = std::nullptr_t, S(*mapping)(F, S) = nullptr, F(*composition)(F, F) = nullptr, F(*id)() = nullptr>
class link_cut_tree {
    static constexpr bool is_pull_type_v = !std::is_same_v<S, std::nullptr_t>;
    static constexpr bool is_push_type_v = !std::is_same_v<F, std::nullptr_t>;

    struct no_value_base {};
    struct sum_base {
        sum_base() : value(e()), sum(e()) {}
        S value, sum;
    };
    struct sum_apply_base {
        sum_apply_base() : value(e()), sum(e()), apply(id()) {}
        S value, sum;
        F apply;
    };
    struct non_evertable_base {};
    struct evertable_base {
        evertable_base() : rev(false) {}
        bool rev;
    };
    using v_base = std::conditional_t<is_push_type_v, sum_apply_base,
        std::conditional_t<is_pull_type_v, sum_base, no_value_base>>;
    using e_base = std::conditional_t<Is_Evertable, evertable_base, non_evertable_base>;

    struct splay_tree_node : public v_base, public e_base {
        splay_tree_node() : v_base(), e_base(), left(-1), right(-1), parent(-1) {}
        int left, right, parent;
    };
    using node = splay_tree_node;
public:
    link_cut_tree() : link_cut_tree(0) {}
    explicit link_cut_tree(int n) : m_size(n), m_nodes(n) {}

    void link(int v, int p) {
        expose(v);
        splay(v);
        expose(p);
        splay(v);
        m_nodes[p].right = v;
        m_nodes[v].parent = p;
        pull(p);
    }

    void cut(int v) {
        expose(v);
        splay(v);
        int p = m_nodes[v].left;
        m_nodes[v].left = -1;
        m_nodes[p].parent = -1;
        pull(v);
    }

    template<bool Always_True = true, std::enable_if_t<Always_True && Is_Evertable>* = nullptr>
    void evert(int v) {
        expose(v);
        splay(v);
        std::swap(m_nodes[v].left, m_nodes[v].right);
        m_nodes[v].rev = true;
    }

    int lowest_common_ancester(int u, int v) {
        expose(u);
        return expose(v);
    }

    template<bool Always_True = true, std::enable_if_t<Always_True && is_pull_type_v>* = nullptr>
    S get(int v) {
        push_down_from_top(v);
        splay(v);
        return m_nodes[v].value;
    }
    template<bool Always_True = true, std::enable_if_t<Always_True && is_pull_type_v>* = nullptr>
    void set(int v, S x) {
        push_down_from_top(v);
        splay(v);
        m_nodes[v].value = x;
        pull(v);
    }
    template<bool Always_True = true, std::enable_if_t<Always_True && is_pull_type_v>* = nullptr>
    S prod(int u, int v) {
        expose(u);
        int w = expose(v);
        splay(u);
        splay(w);
        S sum = m_nodes[w].value;
        if (u != w) {
            sum = op(m_nodes[u].sum, sum);
        }
        if (int r = m_nodes[w].right; r != -1) {
            sum = op(sum, m_nodes[r].sum);
        }
        return sum;
    }

    template<bool Always_True = true, std::enable_if_t<Always_True && is_push_type_v>* = nullptr>
    void apply(int v, F f) {
        push_down_from_top(v);
        m_nodes[v].value = mapping(f, m_nodes[v].value);
        pull_to_top(v);
    }
    template<bool Always_True = true, std::enable_if_t<Always_True && is_push_type_v>* = nullptr>
    void apply(int u, int v, F f) {
        expose(u);
        int w = expose(v);
        splay(u);
        splay(w);
        m_nodes[w].value = mapping(f, m_nodes[w].value);
        if (u != w) {
            apply_to_node(u, f);
        }
        if (int r = m_nodes[w].right; r != -1) {
            apply_to_node(r, f);
        }
    }

    void debug() {
        std::vector<bool> visited(m_size);
        auto dfs = [&](auto self, int v, int p) -> void {
            visited[v] = true;
            S sum = m_nodes[v].value;
            if (int l = m_nodes[v].left; l != -1) {
                self(self, l, v);
                sum = op(m_nodes[l].sum, sum);
            }
            if (int r = m_nodes[v].right; r != -1) {
                self(self, r, v);
                sum = op(sum, m_nodes[r].sum);
            }
            bool ok = m_nodes[v].sum == sum;
            if (!ok) {
                std::cout << v << std::endl;
            }
        };
        for (int v = 0; v < m_size; ++v) {
            if (visited[v]) continue;
            if (!is_splay_tree_root(v)) continue;
            dfs(dfs, v, -1);
        }
    }

private:
    int expose(int v) {
        int pre = -1;
        for (int current = v; current != -1; current = m_nodes[current].parent) {
            push_down_from_top(current);
            splay(current);
            m_nodes[current].right = pre;
            pull(current);
            pre = current;
        }
        return pre;
    }

    void splay(int v) {
        while (!is_splay_tree_root(v)) {
            int p = m_nodes[v].parent;
            int gp = m_nodes[p].parent;
            if (!is_splay_tree_root(p)) {
                int ggp = m_nodes[gp].parent;
                if (ggp != -1) {
                    if (gp == m_nodes[ggp].left) m_nodes[ggp].left = v;
                    else if (gp == m_nodes[ggp].right) m_nodes[ggp].right = v;
                }
                m_nodes[v].parent = ggp;
                if (v == m_nodes[p].left && p == m_nodes[gp].right) {
                    int b = m_nodes[v].right, c = m_nodes[v].left;
                    m_nodes[v].right = p;
                    m_nodes[p].parent = v;
                    m_nodes[v].left = gp;
                    m_nodes[gp].parent = v;
                    m_nodes[p].left = b;
                    if (b != -1) m_nodes[b].parent = p;
                    m_nodes[gp].right = c;
                    if (c != -1) m_nodes[c].parent = gp;
                }
                else if (v == m_nodes[p].right && p == m_nodes[gp].left) {
                    int b = m_nodes[v].left, c = m_nodes[v].right;
                    m_nodes[v].left = p;
                    m_nodes[p].parent = v;
                    m_nodes[v].right = gp;
                    m_nodes[gp].parent = v;
                    m_nodes[p].right = b;
                    if (b != -1) m_nodes[b].parent = p;
                    m_nodes[gp].left = c;
                    if (c != -1) m_nodes[c].parent = gp;
                }
                else if (v == m_nodes[p].left && p == m_nodes[gp].left) {
                    int b = m_nodes[v].right, c = m_nodes[p].right;
                    m_nodes[v].right = p;
                    m_nodes[p].parent = v;
                    m_nodes[p].right = gp;
                    m_nodes[gp].parent = p;
                    m_nodes[p].left = b;
                    if (b != -1) m_nodes[b].parent = p;
                    m_nodes[gp].left = c;
                    if (c != -1) m_nodes[c].parent = gp;
                }
                else {
                    int b = m_nodes[v].left, c = m_nodes[p].left;
                    m_nodes[v].left = p;
                    m_nodes[p].parent = v;
                    m_nodes[p].left = gp;
                    m_nodes[gp].parent = p;
                    m_nodes[p].right = b;
                    if (b != -1) m_nodes[b].parent = p;
                    m_nodes[gp].right = c;
                    if (c != -1) m_nodes[c].parent = gp;
                }
                pull(gp);
                pull(p);
                pull(v);
            }
            else {
                if (v == m_nodes[p].left) {
                    int x = m_nodes[v].right;
                    m_nodes[p].left = x;
                    if (x != -1) m_nodes[x].parent = p;
                    m_nodes[v].parent = m_nodes[p].parent;
                    m_nodes[v].right = p;
                    m_nodes[p].parent = v;
                }
                else {
                    int x = m_nodes[v].left;
                    m_nodes[p].right = x;
                    if (x != -1) m_nodes[x].parent = p;
                    m_nodes[v].parent = m_nodes[p].parent;
                    m_nodes[v].left = p;
                    m_nodes[p].parent = v;
                }
                pull(p);
                pull(v);
            }
        }
    }
    inline int is_splay_tree_root(int v) const {
        int p = m_nodes[v].parent;
        return p == -1 || (m_nodes[p].left != v && m_nodes[p].right != v);
    }

    template<bool Always_True = true, std::enable_if_t<Always_True && is_pull_type_v>* = nullptr>
    inline void pull(int v) {
        S sum = m_nodes[v].value;
        if (int l = m_nodes[v].left; l != -1) sum = op(m_nodes[l].sum, sum);
        if (int r = m_nodes[v].right; r != -1) sum = op(sum, m_nodes[r].sum);
        m_nodes[v].sum = sum;
    }
    template<bool Always_True = true, std::enable_if_t<Always_True && !is_pull_type_v>* = nullptr>
    inline void pull(int) {}

    template<bool Always_True = true, std::enable_if_t<Always_True && is_push_type_v>* = nullptr>
    inline void update_push(int v) { pull(v); }
    template<bool Always_True = true, std::enable_if_t<Always_True && !is_push_type_v>* = nullptr>
    inline void update_push(int) {}

    template<bool Always_True = true, std::enable_if_t<Always_True && is_push_type_v>* = nullptr>
    inline void push(int v) {
        if (m_nodes[v].apply == id()) return;
        if (int l = m_nodes[v].left; l != -1) {
            apply_to_node(l, m_nodes[v].apply);
        }
        if (int r = m_nodes[v].right; r != -1) {
            apply_to_node(r, m_nodes[v].apply);
        }
        m_nodes[v].apply = id();
        if constexpr (Is_Evertable) {
            eval_rev(v);
        }
    }
    template<bool Always_True = true, std::enable_if_t<Always_True && !is_push_type_v>* = nullptr>
    inline void push(int v) {
        if constexpr (Is_Evertable) {
            eval_rev(v);
        }
    }
    template<bool Always_True = true, std::enable_if_t<Always_True&& is_push_type_v>* = nullptr>
    inline void apply_to_node(int v, F f) {
        m_nodes[v].value = mapping(f, m_nodes[v].value);
        m_nodes[v].sum = mapping(f, m_nodes[v].sum);
        m_nodes[v].apply = composition(f, m_nodes[v].apply);
    }
    template<bool Always_True = true, std::enable_if_t<Always_True && Is_Evertable>* = nullptr>
    inline void eval_rev(int v) {
        if (m_nodes[v].rev) {
            if (int l = m_nodes[v].left; l != -1) {
                std::swap(m_nodes[l].left, m_nodes[l].right);
                m_nodes[l].rev = true;
            }
            if (int r = m_nodes[v].right; r != -1) {
                std::swap(m_nodes[r].left, m_nodes[r].right);
                m_nodes[r].rev = true;
            }
            m_nodes[v].rev = false;
        }
    }
    template<bool Always_True = true, std::enable_if_t<Always_True && !Is_Evertable>* = nullptr>
    inline void eval_rev(int v) {}

    void pull_to_top(int v) {
        while (v != -1) {
            pull(v);
            v = m_nodes[v].parent;
        }
    }
    void update_push_to_top(int v) {
        while (v != -1) {
            update_push(v);
            v = m_nodes[v].parent;
        }
    }
    void push_down_from_top(int v) {
        if (m_nodes[v].parent != -1) {
            push_down_from_top(m_nodes[v].parent);
        }
        push(v);
    }
private:
    int m_size;
    std::vector<node> m_nodes;
};

}  // namespace atcoder_ex

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = std::pair<ll, int>;
constexpr P op(P l, P r) { return P(l.first + r.first, l.second + r.second); }
constexpr P e() { return P(0, 1); }
constexpr P mapping(int l, P r) { return P(r.first + (ll)l * r.second, r.second); }
constexpr int composition(int l, int r) { return l + r; }
constexpr int id() { return 0; }

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

    int N;
    cin >> N;
    vector<vector<int>> tree(N);
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    atcoder_ex::link_cut_tree<false, P, op, e, int, mapping, composition, id> lct(N);
    auto dfs = [&](auto self, int v, int p) -> void {
        for (int u : tree[v]) {
            if (u == p) continue;
            lct.link(u, v);
            self(self, u, v);
        }
    };
    dfs(dfs, 0, -1);

    int Q;
    cin >> Q;
    ll ans = 0;
    for (int i = 0; i < Q; ++i) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        lct.apply(a, b, 1);
        ans += lct.prod(a, b).first;
    }
    cout << ans << endl;
}
yukicoder

結果

テストケース

ソースコード
