結果

問題 No.2163 LCA Sum Query
ユーザー akakimidoriakakimidori
提出日時 2022-12-09 18:31:59
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 6,969 bytes
コンパイル時間 972 ms
コンパイル使用メモリ 113,912 KB
最終ジャッジ日時 2024-04-27 04:19:24
合計ジャッジ時間 2,202 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function 'void run()':
main.cpp:193:27: error: unable to deduce 'auto' from 'add'
  193 |     segtree<i64, add, zero> cnt(n);
      |                           ^
main.cpp:193:27: note:   couldn't deduce template parameter 'auto'
main.cpp:193:27: error: unable to deduce 'auto' from 'zero'
main.cpp:193:27: note:   couldn't deduce template parameter 'auto'
main.cpp:194:73: error: unable to deduce 'auto' from 'add'
  194 |     lazy_segtree<array<i64, 2>, add, zero, array<i64, 1>, map, add, zero> fix_root(n);
      |                                                                         ^
main.cpp:194:73: note:   couldn't deduce template parameter 'auto'
main.cpp:194:73: error: unable to deduce 'auto' from 'zero'
main.cpp:194:73: note:   couldn't deduce template parameter 'auto'
main.cpp:194:73: error: unable to deduce 'auto' from 'map'
main.cpp:194:73: note:   couldn't deduce template parameter 'auto'
main.cpp:194:73: error: unable to deduce 'auto' from 'add'
main.cpp:194:73: note:   couldn't deduce template parameter 'auto'
main.cpp:194:73: error: unable to deduce 'auto' from 'zero'
main.cpp:194:73: note:   couldn't deduce template parameter 'auto'
main.cpp:195:73: error: unable to deduce 'auto' from 'add'
  195 |     lazy_segtree<array<i64, 4>, add, zero, array<i64, 2>, map, add, zero> move_root(n);
      |                                                                         ^
main.cpp:195:73: note:   couldn't deduce template parameter 'auto'
main.cpp:195:73: error: unable to deduce 'auto' from 'zero'
main.cpp:195:73: note:   couldn't deduce template parameter 'auto'
main.cpp:195:73: error: unable to deduce 'auto' from 'map'
main.cpp:195:73: note:   couldn't deduce template parameter 'auto'
main.cpp:195:73: error: unable to deduce 'auto' from 'add'
main.cpp:195:73: note:   couldn't deduce template parameter 'auto'
main.cpp:195:73: error: unable to deduce 'auto' from 'zero'
main.cpp:195:73: note:   couldn't deduce template parameter 'auto'
main.cpp:199

ソースコード

diff # 

#include <algorithm>
#include <atcoder/lazysegtree>
#include <atcoder/segtree>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <limits>
#include <queue>
#include <string>
#include <vector>

using namespace std;
using namespace atcoder;

using i64 = int64_t;
using u64 = uint64_t;
using i32 = int32_t;
using u32 = uint32_t;

#define REP(i, s, t) for (i32 i = (s); i < (t); ++i)

template <class T>
std::vector<T> vec(T elem, int len) {
    return std::vector<T>(len, elem);
}

struct HLD {
    const i32 size;
    vector<vector<i32>> graph;
    vector<i32> left;
    vector<i32> right;
    vector<i32> vertex;
    vector<i32> parent;
    vector<i32> path_root;
    HLD(const i32 size)
        : size(size),
          graph(size),
          left(size),
          right(size),
          vertex(size),
          parent(size, -1),
          path_root(size) {}
    void add_edge(const i32 a, const i32 b) {
        assert(0 <= min(a, b) && max(a, b) < size);
        graph[a].emplace_back(b);
        graph[b].emplace_back(a);
    }
    void build(const i32 root) {
        dfs_size(root, -1);
        i32 id = 0;
        path_root[root] = root;
        dfs_ord(root, id);
    }
    i32 dfs_size(const i32 v, const i32 p) {
        i32 s = 1;
        i32 max = 0;
        i32 max_pos = -1;
        for (i32 i = 0; i < (i32)graph[v].size(); ++i) {
            const i32 u = graph[v][i];
            if (u == p) continue;
            parent[u] = v;
            const i32 c = dfs_size(u, v);
            if (c > max) {
                max = c;
                max_pos = i;
            }
            s += c;
        }
        if (max_pos >= 0) {
            swap(graph[v][max_pos], graph[v][0]);
        }
        return s;
    }
    void dfs_ord(const i32 v, i32 &id) {
        left[v] = id;
        vertex[id] = v;
        id += 1;
        for (i32 i = 0; i < (i32)graph[v].size(); ++i) {
            const i32 u = graph[v][i];
            if (u == parent[v]) continue;
            if (i == 0) {
                path_root[u] = path_root[v];
                dfs_ord(u, id);
            } else {
                path_root[u] = u;
                dfs_ord(u, id);
            }
        }
        right[v] = id;
    }
    pair<i32, i32> subtree(const i32 v) {
        assert(v < size);
        return make_pair(left[v], right[v]);
    }
    i32 next(const i32 s, i32 t) {
        assert(0 <= min(s, t) && max(s, t) < size && s != t);
        const auto [x, y] = subtree(s);
        const auto [z, w] = subtree(t);
        if (!(x <= z && w <= y)) {
            return parent[s];
        }
        i32 pre = t;
        while (path_root[s] != path_root[t]) {
            pre = path_root[t];
            t = parent[pre];
        }
        return t == s ? pre : vertex[x + 1];
    }
    vector<pair<i32, i32>> path(i32 s, i32 t) {
        assert(0 <= min(s, t) && max(s, t) < size && s != t);
        static pair<i32, i32> a[24];
        static pair<i32, i32> b[24];
        i32 x = 0;
        i32 y = 0;
        while (path_root[s] != path_root[t]) {
            if (left[s] < left[t]) {
                const i32 p = path_root[t];
                b[y++] = make_pair(left[p], left[t] + 1);
                t = parent[p];
            } else {
                const i32 p = path_root[s];
                a[x++] = make_pair(left[p], left[s] + 1);
                s = parent[p];
            }
        }
        if (left[s] <= left[t]) {
            b[y++] = make_pair(left[s], left[t] + 1);
        } else {
            a[x++] = make_pair(left[t], left[s] + 1);
        }
        vector<pair<i32, i32>> res(x + y);
        for (i32 i = 0; i < x; ++i) {
            res[i] = a[i];
        }
        for (i32 i = 0; i < y; ++i) {
            res[x + i] = b[y - 1 - i];
        }
        return res;
    }
};

i32 read_int(void) {
    i32 v;
    cin >> v;
    return v;
}

i64 add(i64 a, i64 b) { return a + b; }
i64 zero() { return 0; }

template <size_t K>
array<i64, K> add(const array<i64, K> a, const array<i64, K> b) {
    array<i64, K> c;
    REP(i, 0, K) { c[i] = a[i] + b[i]; }
    return c;
}

template <size_t K>
array<i64, K> zero() {
    array<i64, K> c{};
    return c;
}

template <size_t K>
array<i64, 1 << K> map(const array<i64, K> f, array<i64, 1 << K> x) {
    array<i64, 1 << K> res(x);
    REP(bit, 1, 1 << K) {
        for (i32 p = bit; p > 0; p = (p - 1) & bit) {
            i64 v = x[p ^ bit];
            REP(i, 0, K) {
                if ((p >> i) & 1) {
                    v *= f[i];
                }
            }
            res[bit] += v;
        }
    }
    return res;
}

void run(void) {
    const i32 n = read_int() + 1;
    const i32 q = read_int();
    HLD hld(n);
    hld.add_edge(0, 1);
    REP(i, 2, n) {
        const i32 a = read_int();
        const i32 b = read_int();
        hld.add_edge(a, b);
    }
    hld.build(0);
    segtree<i64, add, zero> cnt(n);
    lazy_segtree<array<i64, 2>, add, zero, array<i64, 1>, map, add, zero> fix_root(n);
    lazy_segtree<array<i64, 4>, add, zero, array<i64, 2>, map, add, zero> move_root(n);
    REP(i, 1, n) {
        const i64 v = hld.vertex[i];
        const i64 p = hld.parent[v];
        move_root.set(i, {v - p, 0, 0, 0});
    }
    vector<i32> state(n, 0);
    REP(i, 0, q) {
        const i32 u = read_int();
        const i32 sign = (state[u] ^ 1) - state[u];
        move_root.apply(0, n, {sign, 0});
        i32 sub = state[u];
        auto path = hld.path(u, 0);
        for (auto [l, r] : path) {
            move_root.apply(l, r, {-sign, sign});
            const i32 v = hld.vertex[r - 1];
            const auto [s, t] = hld.subtree(v);
            const i32 c = cnt.prod(s, t) - sub;
            const auto x = fix_root.get(r - 1);
            fix_root.set(r - 1, {x[0] + sign * v, x[1] + (i64)sign * c * v});
            fix_root.apply(l, r - 1, {sign});
            const auto [a, b] = hld.subtree(hld.vertex[l]);
            sub = cnt.prod(a, b);
        }
        state[u] ^= 1;
        cnt.set(hld.left[u], state[u]);
        const i32 r = read_int();
        const i32 v = read_int();
        i64 ans = 0;
        if (hld.left[v] <= hld.left[r] && hld.right[r] <= hld.right[v]) {
            ans = fix_root.prod(0, n)[1];
            const auto path = hld.path(0, v);
            for (auto [l, r] : path) {
                ans += move_root.prod(l, r)[3];
            }
            if (r != v) {
                const i32 x = hld.next(v, r);
                const auto [s, t] = hld.subtree(x);
                const i32 c = cnt.prod(0, n);
                const i32 d = cnt.prod(s, t);
                ans -= (i64)v * d * (c - d);
                ans -= fix_root.prod(s, t)[1];
            }
        } else {
            const auto [l, r] = hld.subtree(v);
            ans = fix_root.prod(l, r)[1];
        }
        cout << ans << "\n";
    }
}

int main(void) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    run();
    return 0;
}
0