結果

問題 No.2163 LCA Sum Query
ユーザー akakimidoriakakimidori
提出日時 2022-12-09 21:33:53
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 4,809 bytes
コンパイル時間 1,373 ms
コンパイル使用メモリ 120,624 KB
実行使用メモリ 16,928 KB
最終ジャッジ日時 2024-04-24 12:36:46
合計ジャッジ時間 11,508 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 165 ms
5,376 KB
testcase_13 AC 395 ms
8,704 KB
testcase_14 AC 277 ms
9,728 KB
testcase_15 AC 57 ms
5,376 KB
testcase_16 AC 213 ms
8,832 KB
testcase_17 AC 195 ms
5,888 KB
testcase_18 AC 103 ms
5,376 KB
testcase_19 AC 72 ms
5,376 KB
testcase_20 AC 47 ms
6,272 KB
testcase_21 AC 135 ms
6,016 KB
testcase_22 TLE -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <limits>
#include <queue>
#include <string>
#include <vector>

using namespace std;

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)

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

void run(void) {
    const i32 n = read_int() + 1;
    const i32 q = read_int();
    HLD hld(n);
    hld.add_edge(0, 1);
    vector<vector<i32>> graph(n + 1);
    REP(i, 2, n) {
        const i32 a = read_int();
        const i32 b = read_int();
        hld.add_edge(a, b);
        graph[a].emplace_back(b);
        graph[b].emplace_back(a);
    }
    hld.build(0);
    vector<i32> state(n, 0);
    REP(i, 0, q) {
        const i32 u = read_int();
        const i32 r = read_int();
        const i32 v = read_int();
        state[u] ^= 1;
        i64 ans = 0;
        auto dfs = [&](auto self, i32 v, i32 p) -> i64 {
            i64 s = state[v];
            for (auto u: graph[v]) {
                if (u != p) {
                    i64 c = self(self, u, v);
                    ans += (i64)v * s * c;
                    s += c;
                }
            }
            return s;
        };
        i32 p = r == v ? -1 : hld.next(v, r);
        dfs(dfs, v, p);
        cout << ans << "\n";
    }
}

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