結果

問題 No.2163 LCA Sum Query
コンテスト
ユーザー akakimidori
提出日時 2022-12-13 03:35:12
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 6,791 bytes
コンパイル時間 1,223 ms
コンパイル使用メモリ 114,164 KB
最終ジャッジ日時 2024-11-15 03:05:12
合計ジャッジ時間 2,898 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function 'void run()':
main.cpp:183:37: error: unable to deduce 'auto' from 'add'
  183 |     segtree<array<i64, 2>, add, zero> sum(n);
      |                                     ^
main.cpp:183:37: note:   couldn't deduce template parameter 'auto'
main.cpp:183:37: error: unable to deduce 'auto' from 'zero'
main.cpp:183:37: note:   couldn't deduce template parameter 'auto'
main.cpp:184:73: error: unable to deduce 'auto' from 'add'
  184 |     lazy_segtree<array<i64, 3>, add, zero, array<i64, 1>, map, add, zero>
      |                                                                         ^
main.cpp:184:73: note:   couldn't deduce template parameter 'auto'
main.cpp:184:73: error: unable to deduce 'auto' from 'zero'
main.cpp:184:73: note:   couldn't deduce template parameter 'auto'
main.cpp:184:73: error: unable to deduce 'auto' from 'map'
main.cpp:184:73: note:   couldn't deduce template parameter 'auto'
main.cpp:184:73: error: unable to deduce 'auto' from 'add'
main.cpp:184:73: note:   couldn't deduce template parameter 'auto'
main.cpp:184:73: error: unable to deduce 'auto' from 'zero'
main.cpp:184:73: note:   couldn't deduce template parameter 'auto'
main.cpp:186:73: error: unable to deduce 'auto' from 'add'
  186 |     lazy_segtree<array<i64, 4>, add, zero, array<i64, 2>, map, add, zero>
      |                                                                         ^
main.cpp:186:73: note:   couldn't deduce template parameter 'auto'
main.cpp:186:73: error: unable to deduce 'auto' from 'zero'
main.cpp:186:73: note:   couldn't deduce template parameter 'auto'
main.cpp:186:73: error: unable to deduce 'auto' from 'map'
main.cpp:186:73: note:   couldn't deduce template parameter 'auto'
main.cpp:186:73: error: unable to deduce 'auto' from 'add'
main.cpp:186:73: note:   couldn't deduce template parameter 'auto'
main.cpp:186:73: error: unable to deduce 'auto' from 'zero'
main.cpp:186:73: note:   couldn't deduce template parameter 'auto'
main.cpp:191:18: er

ソースコード

diff #
raw source code 

#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;
}

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;
}

array<i64, 3> map(array<i64, 1> f, array<i64, 3> x) {
    return {x[0], x[1] + x[0] * f[0],
            x[2] + 2 * x[1] * f[0] + x[0] * f[0] * f[0]};
}

array<i64, 4> map(array<i64, 2> f, array<i64, 4> x) {
    return {x[0], x[0] * f[0] + x[1], x[0] * f[1] + x[2],
            x[0] * f[0] * f[1] + x[1] * f[1] + x[2] * f[0] + x[3]};
}

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<array<i64, 2>, add, zero> sum(n);
    lazy_segtree<array<i64, 3>, 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];
        fix_root.set(i, {v - p, 0, 0});
        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});
        auto path = hld.path(u, 0);
        for (auto [l, r] : path) {
            fix_root.apply(l, r, {sign});
            move_root.apply(l, r, {-sign, sign});
        }
        state[u] ^= 1;
        if (state[u]) {
            sum.set(hld.left[u], {1, u});
        } else {
            sum.set(hld.left[u], {0, 0});
        }
        auto f1 = [&](const i32 v) -> i64 {
            auto [l, r] = hld.subtree(v);
            auto [c, s] = sum.prod(l, r);
            i64 res = fix_root.prod(l, r)[2] - s;
            if (v > 0) {
                res += c * c * hld.parent[v];
            }
            return res / 2;
        };
        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 = f1(0);
            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 = sum.prod(0, n)[0];
                const i32 d = sum.prod(s, t)[0];
                ans -= (i64)v * d * (c - d);
                ans -= f1(x);
            }
        } else {
            ans = f1(v);
        }
        cout << ans << "\n";
    }
}

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