結果

問題 No.1038 TreeAddQuery
ユーザー potoooooooo
提出日時 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();
      |                              ^

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define MAX_SIZE 100010
// zero-based numbering
template<class T> struct Fenwick {
vector<T> bit; int N;
Fenwick() {}
Fenwick(int n) : N(n) { bit.assign(n+1, 0); }
// add w to a
void 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0