結果

問題 No.899 γatheree
コンテスト
ユーザー QCFium
提出日時 2020-05-08 23:58:14
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 544 ms / 2,000 ms
コード長 2,967 bytes
コンパイル時間 1,106 ms
コンパイル使用メモリ 73,156 KB
実行使用メモリ 14,080 KB
最終ジャッジ日時 2024-07-04 01:19:10
合計ジャッジ時間 13,261 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <queue>
#include <vector>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

struct SegTree {
	int n;
	std::vector<int64_t> sum;
	std::vector<bool> zero;
	SegTree (const std::vector<int> &a) {
		for (n = 1; n < (int) a.size(); n <<= 1);
		sum.resize(n << 1);
		for (int i = 0; i < (int) a.size(); i++) sum[i + n] = a[i];
		for (int i = n; --i; ) fetch(i);
		zero.resize(n << 1);
	}
	void flush(int i) {
		if (zero[i]) {
			sum[i] = 0;
			if (i < n) {
				zero[i << 1] = true;
				zero[i << 1 | 1] = true;
			}
			zero[i] = false;
		}
	}
	void fetch(int i) {
		sum[i] = sum[i << 1] + sum[i << 1 | 1];
	}
	template<class T> void dive(int l, int r, int node, int node_l, int node_r, const T &func) {
		flush(node);
		if (r <= node_l || l >= node_r) return;
		if (l <= node_l && r >= node_r) func(node);
		else {
			int mid = node_l + ((node_r - node_l) >> 1);
			dive(l, r, node << 1, node_l, mid, func);
			dive(l, r, node << 1 | 1, mid, node_r, func);
			fetch(node);
		}
	}
	int64_t get_sum(int l, int r) {
		int64_t res = 0;
		dive(l, r, 1, 0, n, [&] (int node) { res += sum[node]; });
		return res;
	}
	void zero_clear(int l, int r) {
		dive(l, r, 1, 0, n, [&] (int node) { zero[node] = true; flush(node); });
	}
	void add(int i, int64_t val) {
		dive(i, i + 1, 1, 0, n, [&] (int node) { sum[node] += val; });
	}
};


int main() {
	int n = ri();
	std::vector<int> hen[n];
	for (int i = 1; i < n; i++) {
		int a = ri();
		int b = ri();
		hen[a].push_back(b);
		hen[b].push_back(a);
	}
	int weight[n];
	for (auto &i : weight) i = ri();
	
	std::vector<int> init(n);
	int bfs_cnt = 0;
	int ord[n], parent[n];
	std::pair<int, int> lr1[n];
	std::pair<int, int> lr2[n];
	
	std::vector<bool> used(n);
	std::queue<int> que;
	que.push(0);
	used[0] = true;
	while (que.size()) {
		int i = que.front();
		que.pop();
		init[ord[i] = bfs_cnt++] = weight[i];
		lr1[i].first = bfs_cnt + que.size();
		int degree_sum = 0;
		for (auto j : hen[i]) if (!used[j]) {
			degree_sum += hen[j].size() - 1;
			used[j] = true;
			parent[j] = i;
			que.push(j);
			lr1[i].second++;
		}
		lr1[i].second = bfs_cnt + que.size();
		if (i) {
			lr2[parent[i]].first = std::min(lr2[parent[i]].first, lr1[i].first);
			lr2[parent[i]].second = std::max(lr2[parent[i]].second, lr1[i].second);
		}
		lr2[i] = {1000000000, -1000000000};
	}
	
	SegTree tree(init);
	
	int q = ri();
	for (int i = 0; i < q; i++) {
		int x = ri();
		int64_t res = 0;
		auto process = [&] (int l, int r) {
			res += tree.get_sum(l, r);
			tree.zero_clear(l, r);
		};
		if (x) {
			if (parent[x]) process(ord[parent[parent[x]]], ord[parent[parent[x]]] + 1);
			process(ord[parent[x]], ord[parent[x]] + 1);
			process(lr1[parent[x]].first, lr1[parent[x]].second);
		} else process(ord[x], ord[x] + 1);
		process(lr1[x].first, lr1[x].second);
		process(lr2[x].first, lr2[x].second);
		printf("%" PRId64 "\n", res);
		tree.add(ord[x], res);
	}
	
	return 0;
}
0