結果
問題 | No.1038 TreeAddQuery |
ユーザー |
![]() |
提出日時 | 2020-04-24 23:16:24 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,129 ms / 4,000 ms |
コード長 | 4,750 bytes |
コンパイル時間 | 2,235 ms |
コンパイル使用メモリ | 197,844 KB |
実行使用メモリ | 147,996 KB |
最終ジャッジ日時 | 2024-11-25 04:44:40 |
合計ジャッジ時間 | 16,822 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h>int ri() {int n;scanf("%d", &n);return n;}struct Query {int range;int weight;int id;};struct AVL {struct Node {Node *l;Node *r;int size;int height;int key;int val;int64_t sum;Node *fetch() {size = 1 + l->size + r->size;height = 1 + std::max(l->height, r->height);sum = val + l->sum + r->sum;return this;}Node *rotate_l() {Node *new_root = r;r = new_root->l;new_root->l = this;return fetch(), new_root->fetch();}Node *rotate_r() {Node *new_root = l;l = new_root->r;new_root->r = this;return fetch(), new_root->fetch();}int height_diff() { return l->height - r->height; }Node *balance() {int dif = height_diff();if (dif == 2) {if (l->height_diff() < 0) l = l->rotate_l();return rotate_r();} else if (dif == -2) {if (r->height_diff() > 0) r = r->rotate_r();return rotate_l();} else return fetch();}};static Node *nodes, *NONE;Node *root = NONE;static int head;AVL () {if (!head) nodes[head++] = {NONE, NONE, 0, 0, 0, 0, 0};}static Node *insert(Node *node, int key, int val) {if (node == NONE) return &(nodes[head++] = {NONE, NONE, 1, 1, key, val, val});if (key < node->key) node->l = insert(node->l, key, val);else if (key > node->key) node->r = insert(node->r, key, val);else assert(0);return node->balance();}static int64_t sum(Node *node, int r) {if (node == NONE) return 0;if (node->key < r) return node->l->sum + node->val + sum(node->r, r);else return sum(node->l, r);}void insert(int key, int val) { root = insert(root, key, val); }int64_t sum(int r) { return sum(root, r); }static void reset() { if (head) head = 1; }void clear() { root = NONE; }};AVL::Node *AVL::nodes = new Node[5000000], *AVL::NONE = nodes;int AVL::head = 0;std::vector<std::vector<int> > hen;std::vector<int> size;std::vector<bool> alive;std::vector<std::vector<Query> > qs;void dfs1(int i, int prev) {size[i] = qs[i].size() + 1;for (auto j : hen[i]) if (j != prev && alive[j]) {dfs1(j, i);size[i] += size[j];}}int centroid(int i) {dfs1(i, -1);int minimum = (size[i] + 1) / 2;while (1) {int next = -1;for (auto j : hen[i]) if (alive[j] && size[j] < size[i] && size[j] >= minimum) next = j;if (next == -1) break;i = next;}return i;}std::vector<Query> adds, getqs;std::vector<int> depth;void dfs2(int i, int prev) {for (auto j : qs[i]) {if (j.range >= depth[i]) adds.push_back({j.range - depth[i], j.weight, j.id});getqs.push_back({depth[i], 0, j.id});}for (auto j : hen[i]) if (j != prev && alive[j]) {depth[j] = depth[i] + 1;dfs2(j, i);}}std::vector<int64_t> res;void centroid_rec(int i) {// std::cerr << i << " " << centroid(i) << std::endl;i = centroid(i);std::vector<std::pair<int, Query> > add_all, get_all;int group = 0;for (auto j : hen[i]) if (alive[j]) {adds.clear();getqs.clear();depth[j] = 1;dfs2(j, i);for (auto i : adds) add_all.push_back({group, i});for (auto i : getqs) get_all.push_back({group, i});group++;}for (auto j : qs[i]) {add_all.push_back({group, {j.range, j.weight, j.id}});get_all.push_back({group, {0, 0, j.id}});}std::sort(add_all.begin(), add_all.end(), [] (auto &i, auto &j) { return i.second.range > j.second.range; });std::sort(get_all.begin(), get_all.end(), [] (auto &i, auto &j) { return i.second.range > j.second.range; });/*for (auto i : get_all) std::cerr << " GET " << i.second.range << " " << i.second.weight << " " << i.second.id << std::endl;for (auto i : add_all) std::cerr << " ADD " << i.second.range << " " << i.second.weight << " " << i.second.id << std::endl;*/int head = 0;AVL all;AVL each[group + 1];for (auto j : get_all) {while (head < (int) add_all.size() && add_all[head].second.range >= j.second.range) {all.insert(add_all[head].second.id, add_all[head].second.weight);each[add_all[head].first].insert(add_all[head].second.id, add_all[head].second.weight);head++;}res[j.second.id] += all.sum(j.second.id);if (j.first != group) res[j.second.id] -= each[j.first].sum(j.second.id);}alive[i] = false;for (auto j : hen[i]) if (alive[j]) centroid_rec(j);}int main() {int n = ri();int q = ri();hen.resize(n);for (int i = 1; i < n; i++) {int a = ri() - 1;int b = ri() - 1;hen[a].push_back(b);hen[b].push_back(a);}qs.resize(n);for (int i = 0; i < q; i++) {int a = ri() - 1;int b = ri();int c = ri();qs[a].push_back({b, c, i});}size.resize(n);alive.resize(n, true);depth.resize(n);res.resize(q);centroid_rec(0);for (auto i : res) printf("%" PRId64 "\n", i);return 0;}