結果

問題 No.2163 LCA Sum Query
コンテスト
ユーザー akakimidori
提出日時 2022-12-09 21:33:53
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,809 bytes
コンパイル時間 1,656 ms
コンパイル使用メモリ 118,168 KB
実行使用メモリ 16,928 KB
最終ジャッジ日時 2024-11-06 20:31:09
合計ジャッジ時間 12,304 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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