結果

問題 No.1038 TreeAddQuery
ユーザー QCFiumQCFium
提出日時 2020-04-24 23:16:24
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 1,144 ms / 4,000 ms
コード長 4,750 bytes
コンパイル時間 4,045 ms
コンパイル使用メモリ 194,512 KB
実行使用メモリ 147,856 KB
最終ジャッジ日時 2023-08-16 14:58:14
合計ジャッジ時間 16,974 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 9 ms
5,024 KB
testcase_04 AC 10 ms
5,392 KB
testcase_05 AC 9 ms
5,148 KB
testcase_06 AC 8 ms
5,208 KB
testcase_07 AC 13 ms
5,668 KB
testcase_08 AC 603 ms
83,612 KB
testcase_09 AC 694 ms
96,232 KB
testcase_10 AC 713 ms
98,188 KB
testcase_11 AC 726 ms
97,940 KB
testcase_12 AC 757 ms
101,156 KB
testcase_13 AC 1,092 ms
141,808 KB
testcase_14 AC 1,000 ms
129,132 KB
testcase_15 AC 982 ms
124,832 KB
testcase_16 AC 940 ms
121,168 KB
testcase_17 AC 925 ms
119,172 KB
testcase_18 AC 170 ms
32,176 KB
testcase_19 AC 216 ms
37,568 KB
testcase_20 AC 194 ms
36,128 KB
testcase_21 AC 230 ms
42,884 KB
testcase_22 AC 295 ms
54,352 KB
testcase_23 AC 340 ms
59,164 KB
testcase_24 AC 498 ms
81,564 KB
testcase_25 AC 1,144 ms
147,856 KB
testcase_26 AC 654 ms
91,056 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0