Submission #1338561

#TimeUsernameProblemLanguageResultExecution timeMemory
1338561goats_9Synchronization (JOI13_synchronization)C++20
100 / 100
172 ms24156 KiB
/* Author: goats_9 */

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

template <class T>
class fenwick_tree {
public:
	fenwick_tree() : _n(0) {}
	explicit fenwick_tree(int n) : _n(n), data(n + 1) {}

	void update(int p, T x) {
		assert(0 <= p && p < _n);
		for (; p <= _n; p += p & -p) data[p] += T(x);
	}

	T query(int l, int r) {
		assert(0 < l && l <= r && r <= _n);
		return query(r) - query(l - 1);
	}
	
	T query(int r) {
		T s = 0;
		for (; r; r -= r & -r) s += data[r];
		return s;
	}

private:
	int _n;
	std::vector<T> data;
};

constexpr int LOG = 17;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m, q;
	cin >> n >> m >> q;
	vector<pair<int, int>> edges(n);
	vector<vector<int>> g(n + 1), up(n + 1, vector<int> (LOG));
	vector<int> a(n), cnt(n + 1), prev(n + 1), tin(n + 1), tout(n + 1);
	for (int i = 1; i < n; i++) {
		auto& [u, v] = edges[i];
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int timer = 1;
	auto dfs = [&] (auto&& self, int u, int p) -> void {
		up[u][0] = p;
		for (int i = 1; i < LOG; i++) up[u][i] = up[up[u][i - 1]][i - 1];
		cnt[u] = 1;
		tin[u] = timer++;
		for (int v : g[u]) {
			if (v == p) continue;
			self(self, v, u);
		}
		tout[u] = timer;
	};
	dfs(dfs, 1, 0);
	fenwick_tree<int> ft(timer + 1);
	for (int i = 1; i <= n; i++) {
		ft.update(tin[i], -1);
		ft.update(tout[i], 1);
	}
	auto root = [&] (int u) -> int {
		int v = u, z = ft.query(tin[u]);
		for (int i = LOG - 1; i >= 0; i--) {
			if (ft.query(tin[up[v][i]]) == z) v = up[v][i];
		}
		return v;
	};
	while (m--) {
		int x;
		cin >> x;
		auto [u, v] = edges[x];
		if (up[u][0] == v) swap(u, v);
		if (a[x]) {
			cnt[v] = prev[v] = cnt[root(u)];
			ft.update(tin[v], -1);
			ft.update(tout[v], 1);
		} else {
			cnt[root(u)] += cnt[v] - prev[v];
			ft.update(tin[v], 1);
			ft.update(tout[v], -1);
		}
		a[x] ^= 1;
	}
	while (q--) {
		int x;
		cin >> x;
		cout << cnt[root(x)] << '\n';
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...