結果
| 問題 | No.1038 TreeAddQuery |
| ユーザー |
👑  emthrm
|
| 提出日時 | 2020-07-30 16:05:07 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 6,427 bytes |
| コンパイル時間 | 25,875 ms |
| コンパイル使用メモリ | 340,376 KB |
| 最終ジャッジ日時 | 2025-01-12 07:54:07 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 14 TLE * 10 |
ソースコード
#pragma GCC optimize("Ofast", "unroll-loops", "omit-frame-pointer", "inline")#pragma GCC option("arch=native", "tune=native", "no-zero-upper")#pragma GCC target("avx2")#define _USE_MATH_DEFINES#include <bits/stdc++.h>using namespace std;#define FOR(i,m,n) for(int i=(m);i<(n);++i)#define REP(i,n) FOR(i,0,n)#define ALL(v) (v).begin(),(v).end()using ll = long long;const int INF = 0x3f3f3f3f;const ll LINF = 0x3f3f3f3f3f3f3f3fLL;const double EPS = 1e-8;const int MOD = 1000000007;// const int MOD = 998244353;const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }struct IOSetup {IOSetup() {cin.tie(nullptr);ios_base::sync_with_stdio(false);cout << fixed << setprecision(20);}} iosetup;using CostType = bool;struct Edge {int src, dst; CostType cost;Edge(int src, int dst, CostType cost = 0) : src(src), dst(dst), cost(cost) {}inline bool operator<(const Edge &x) const {return cost != x.cost ? cost < x.cost : dst != x.dst ? dst < x.dst : src < x.src;}inline bool operator<=(const Edge &x) const { return !(x < *this); }inline bool operator>(const Edge &x) const { return x < *this; }inline bool operator>=(const Edge &x) const { return !(*this < x); }};struct CentroidDecomposition {int root;vector<vector<int>> comp;vector<int> par;CentroidDecomposition(const vector<vector<Edge>> &graph) : graph(graph) {int n = graph.size();alive.assign(n, true);subtree.resize(n);comp.resize(n);par.assign(n, -1);root = build(0);}private:const vector<vector<Edge>> graph;vector<bool> alive;vector<int> subtree;int build(int s) {int centroid = search_centroid(-1, s, calc_subtree(-1, s) / 2);alive[centroid] = false;for (const Edge &e : graph[centroid]) {if (alive[e.dst]) {comp[centroid].emplace_back(build(e.dst));par[e.dst] = centroid;}}alive[centroid] = true;return centroid;}int calc_subtree(int par, int ver) {subtree[ver] = 1;for (const Edge &e : graph[ver]) {if (e.dst != par && alive[e.dst]) subtree[ver] += calc_subtree(ver, e.dst);}return subtree[ver];}int search_centroid(int par, int ver, int half) {for (const Edge &e : graph[ver]) {if (e.dst != par && alive[e.dst]) {if (subtree[e.dst] > half) return search_centroid(ver, e.dst, half);}}return ver;}};template <typename Abelian>struct BITRangeAdd {BITRangeAdd(int n_, const Abelian UNITY = 0) : n(n_), UNITY(UNITY) {++n;dat_const.assign(n, UNITY);dat_linear.assign(n, UNITY);}void add(int left, int right, Abelian val) {if (right < ++left) return;for (int i = left; i < n; i += i & -i) {dat_const[i] -= val * (left - 1);dat_linear[i] += val;}for (int i = right + 1; i < n; i += i & -i) {dat_const[i] += val * right;dat_linear[i] -= val;}}Abelian sum(int idx) {Abelian res = UNITY;for (int i = idx; i > 0; i -= i & -i) res += dat_linear[i];res *= idx;for (int i = idx; i > 0; i -= i & -i) res += dat_const[i];return res;}Abelian sum(int left, int right) {if (right <= left) return UNITY;return sum(right) - sum(left);}Abelian operator[](const int idx) { return sum(idx, idx + 1); }int n;private:const Abelian UNITY;vector<Abelian> dat_const, dat_linear;};int main() {int n, q; cin >> n >> q;vector<vector<Edge>> graph(n);REP(_, n - 1) {int a, b; cin >> a >> b; --a; --b;graph[a].emplace_back(a, b);graph[b].emplace_back(b, a);}CentroidDecomposition cd(graph);vector<bool> visited(n, false);vector<unordered_map<int, int>> mp;vector<vector<int>> resp(n), depth;vector<BITRangeAdd<ll>> bit;vector<unordered_map<int, pair<int, pair<int, int>>>> minus(n);vector<BITRangeAdd<ll>> bit2;function<void(int)> rec = [&](int root) {visited[root] = true;int idx = mp.size();mp.emplace_back();mp[idx][root] = 0;resp[root].emplace_back(idx);depth.emplace_back(vector<int>{0});vector<int> que{root};for (int dep = 1; !que.empty(); ++dep) {vector<int> nx;for (int ver : que) {for (const Edge &e : graph[ver]) {if (!visited[e.dst] && mp[idx].count(e.dst) == 0) {int sz = mp[idx].size();mp[idx][e.dst] = sz;resp[e.dst].emplace_back(idx);depth[idx].emplace_back(dep);nx.emplace_back(e.dst);}}}que.swap(nx);}bit.emplace_back(mp[idx].size());minus[root][idx] = {-1, {-1, -1}};int sum_dep = 0;for (const Edge &dst : graph[root]) {if (visited[dst.dst]) continue;vector<pair<int, int>> aft;int max_depth = 0;function<void(int, int, int)> dfs = [&](int par, int ver, int dep) {chmax(max_depth, dep);aft.emplace_back(ver, dep);for (const Edge &e : graph[ver]) {if (!visited[e.dst] && e.dst != par) dfs(ver, e.dst, dep + 1);}};dfs(root, dst.dst, 1);for (auto [ver, dep] : aft) minus[ver][idx] = {sum_dep + dep, {sum_dep, sum_dep + max_depth}};sum_dep += max_depth + 1;}bit2.emplace_back(sum_dep);for (int e : cd.comp[root]) {if (!visited[e]) rec(e);}};rec(cd.root);while (q--) {int x, y, z; cin >> x >> y >> z; --x;ll ans = 0;for (int idx : resp[x]) {ans += bit[idx][mp[idx][x]];auto [dep, ignore] = minus[x][idx];if (dep != -1) ans -= bit2[idx][dep];}cout << ans << '\n';for (int idx : resp[x]) {int ver = mp[idx][x], dist = y - depth[idx][ver];if (dist >= 0) {int l = 0, r = depth[idx].size();while (r - l > 1) {int mid = (l + r) >> 1;(depth[idx][mid] <= dist ? l : r) = mid;}bit[idx].add(0, l + 1, z);auto [dep, mnmx] = minus[x][idx];if (dep != -1) bit2[idx].add(mnmx.first, min(mnmx.first + dist, mnmx.second) + 1, z);}}}return 0;}