結果
| 問題 | No.1038 TreeAddQuery |
| ユーザー |
 potoooooooo
|
| 提出日時 | 2020-05-07 22:02:46 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2,542 ms / 4,000 ms |
| コード長 | 4,606 bytes |
| コンパイル時間 | 6,632 ms |
| コンパイル使用メモリ | 231,952 KB |
| 最終ジャッジ日時 | 2025-01-10 07:34:57 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 24 |
ソースコード
#include <bits/stdc++.h>using namespace std;// zero-based numberingtemplate<class T> struct Fenwick {vector<T> bit; int N;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); }};template<class Cost = int>struct Edge {int from, to;Cost cost;Edge(const int &from = -1, const int &to = -1, const Cost &cost = 1): from(from), to(to), cost(cost) {}bool operator<(const Edge<Cost> &rhs) const { return this->cost < rhs.cost; }bool operator>(const Edge<Cost> &rhs) const { return this->cost > rhs.cost; }};template<class Cost = int>struct Graph : vector<vector<Edge<Cost>>> {int n;Graph(int _n = 0) : n(_n) { this->resize(n); }void add_edge(const int &src, const int &dst, const Cost &cost = 1) {assert(0 <= src && src < n && 0 <= dst && dst < n);(*this)[src].emplace_back(src, dst, cost);}void add_biedge(const int &src, const int &dst, const Cost &cost = 1) {add_edge(src, dst, cost);add_edge(dst, src, cost);}};template<class Cost = int>struct CentroidDecomposition : Graph<Cost> {using Graph<Cost>::n;Graph<Cost> &g = (*this);vector<int> sz;vector<bool> cut;queue<int> que;CentroidDecomposition(int _n) : Graph<Cost>(_n) {sz.assign(n, 0);cut.assign(n, false);que.emplace(0);}int find(int curr) {auto dfs = [&](auto &&self, int curr, int prev) -> void {sz[curr] = 1;for (auto &e: g[curr]) {if (e.to == prev || cut[e.to]) continue;self(self, e.to, curr);sz[curr] += sz[e.to];}};dfs(dfs, curr, -1);int total = sz[curr];while (true) {int next = -1;for (auto &e: g[curr]) {if (cut[e.to] || sz[e.to] > sz[curr]) continue;if (sz[e.to] * 2 > total) next = e.to;}if (next == -1) break;curr = next;}cut[curr] = true;return curr;}int centroid() {if (que.empty()) return -1;int c = que.front(); que.pop();c = find(c);for (auto &e: g[c]) {if (!cut[e.to]) que.push(e.to);}return c;}};int main() {cin.tie(nullptr);ios::sync_with_stdio(false);int N, Q; cin >> N >> Q;CentroidDecomposition<> g(N);for (int i = 0; i < N-1; i++) {int u, v; cin >> u >> v;g.add_biedge(--u, --v);}int idx = 0;vector<vector<int>> hcount;vector<Fenwick<long long>> fv;vector<vector<tuple<int, int, int, bool>>> w(N); // {idx, id, height, rev}while (true) {int curr = g.centroid();if (curr == -1) break;auto bfs = [&](int curr, int prev, bool rev = false) {vector<int> res;int c, p, h, id = 0;queue<tuple<int, int, int>> que;que.emplace(curr, prev, 0);while (!que.empty()) {tie(c, p, h) = que.front(); que.pop();w[c].emplace_back(idx, id++, h, rev);if (res.size() == h) res.emplace_back(1);else res[h]++;for (auto &e: g[c]) {if (g.cut[e.to] || e.to == p) continue;que.emplace(e.to, c, h+1);}}for (int i = 1; i < res.size(); i++) res[i] += res[i-1];fv.emplace_back(id+1);hcount.emplace_back(res), idx++;};bfs(curr, -1);for (auto &e: g[curr]) {if (!g.cut[e.to]) bfs(e.to, curr, true);}}while (Q--) {int x, y; long long z;cin >> x >> y >> z;long long ans = 0;for (auto &iter: w[--x]) {int idx, id, h; bool rev;tie(idx, id, h, rev) = iter;ans += rev ? -fv[idx].sum(id+1) : fv[idx].sum(id+1);int d = rev ? y-h-2 : y-h;if (d < 0) continue;d = min(d, (int) hcount[idx].size()-1);fv[idx].add(0, z);fv[idx].add(hcount[idx][d], -z);}cout << ans << "\n";}return 0;}