結果
問題 | No.1038 TreeAddQuery |
ユーザー |
|
提出日時 | 2020-04-25 21:06:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,646 ms / 4,000 ms |
コード長 | 3,504 bytes |
コンパイル時間 | 2,746 ms |
コンパイル使用メモリ | 213,580 KB |
最終ジャッジ日時 | 2025-01-10 01:38:05 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
コンパイルメッセージ
In member function ‘Fenwick<long long int>& Fenwick<long long int>::operator=(Fenwick<long long int>&&)’, inlined from ‘Info& Info::operator=(Info&&)’ at main.cpp:24:8, inlined from ‘centroid(int)::<lambda(int, int)>’ at main.cpp:67:30: main.cpp:6:26: warning: ‘<unnamed>.Info::fw.Fenwick<long long int>::N’ is used uninitialized [-Wuninitialized] 6 | template<class T> struct Fenwick { | ^~~~~~~ main.cpp: In lambda function: main.cpp:67:30: note: ‘<anonymous>’ declared here 67 | F[curr][root] = Info(); | ^
ソースコード
#include <bits/stdc++.h>using namespace std;#define MAX_SIZE 100010// zero-based numberingtemplate<class T> struct Fenwick {vector<T> bit; int N;Fenwick() {}Fenwick(int n) : N(n) { bit.assign(n+1, 0); }// add w to avoid add(int a, T w) {for (int x = ++a; x <= N; x += x & -x) bit[x] += w;}// sum [0, a)T sum(int a) {T ret = 0;for (int x = a; x > 0; x -= x & -x) ret += bit[x];return ret;}// sum [a, b)T sum(int a, int b) { return sum(b) - sum(a); }};struct Info {vector<int> h;Fenwick<long long> fw;int max_h = 0;Info() : h{{0}} {}Info(int sz) : fw(sz+2), h{{0}} {};};vector<int> e[MAX_SIZE];int sz[MAX_SIZE];bool cut[MAX_SIZE];unordered_map<int, Info> F[MAX_SIZE];vector<array<int, 4>> v[MAX_SIZE];int find_centroid(int curr) {auto dfs = [&](auto f, int curr, int prev) -> void {sz[curr] = 1;for (auto &to: e[curr]) {if (to == prev || cut[to]) continue;f(f, to, curr);sz[curr] += sz[to];}};dfs(dfs, curr, -1);int all = sz[curr];while (true) {int next = -1;for (auto &to: e[curr]) {if (cut[to] || sz[to] > sz[curr]) continue;if (sz[to] * 2 >= all) next = to;}if (next == -1) break;curr = next;}cut[curr] = true;return curr;}long long cntt = 0;void centroid(int curr) {curr = find_centroid(curr);auto bfs = [&](int root, int prev) {F[curr][root] = Info();cntt += sz[root];auto &u = F[curr][root];queue<array<int, 3>> q;q.push({root, prev, 0});int cnt = 0;while (!q.empty()) {auto c = q.front(); q.pop();v[c[0]].push_back({curr, root, cnt, c[2]});if (u.max_h < c[2]) {u.max_h = c[2];u.h.emplace_back(0);}u.h.back() = cnt++;for (auto &x: e[c[0]]) {if (x == c[1] || cut[x]) continue;q.push({x, c[0], c[2]+1});}}F[curr][root].fw = Fenwick<long long>(cnt);};bfs(curr, -1);for (auto &to: e[curr]) {if (cut[to]) continue;bfs(to, curr);}for (auto &to: e[curr]) {if (!cut[to]) centroid(to);}}long long f(int x) {long long ans = 0;for (auto &[c, r, i, h] : v[x]) {ans += F[c][r].fw.sum(i+1);}return ans;}long long query(int x, int y, long long z) {long long ans = 0;for (auto &[c, r, i, h] : v[x]) {ans += F[c][r].fw.sum(i+1);int d = (c == r) ? y-h : y-h-2;d = min(d, F[c][r].max_h);if (d >= 0) {long long w = (c == r) ? z : -z;F[c][r].fw.add(0, w);F[c][r].fw.add(F[c][r].h[d]+1, -w);}}return ans;}int main() {cin.tie(nullptr);ios::sync_with_stdio(false);int n, q; cin >> n >> q;for (int i = 0; i < n-1; i++) {int u, v; cin >> u >> v; u--; v--;e[u].emplace_back(v);e[v].emplace_back(u);}centroid(0);auto debug = [&]() {for (int j = 0; j < n; j++) cout << f(j) << " ";cout << "\n";};for (int i = 0; i < q; i++) {int x, y; long long z;cin >> x >> y >> z;cout << query(--x, y, z) << "\n";// debug();}return 0;}