Submission #1320816

#TimeUsernameProblemLanguageResultExecution timeMemory
1320816ppmn_6Synchronization (JOI13_synchronization)C++20
100 / 100
201 ms37544 KiB
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// https://codeforces.com/blog/entry/79148
class Timer: chrono::high_resolution_clock {
    const time_point start_time;
public:
    Timer(): start_time(now()) {}
    rep elapsed_time() const {
		return chrono::duration_cast<chrono::milliseconds>(now() - start_time).count();
	}
} timer;

struct FenwickTree {
	int n;
	vector<int> tree;
	FenwickTree(int n_) {
		n = n_;
		tree.resize(n + 1, 0);
	}
	void update(int p, int k) {
		while (p <= n) {
			tree[p] += k;
			p += p & (-p);
		}
	}
	int prefixQuery(int r) {
		int res = 0;
		while (r) {
			res += tree[r];
			r -= r & (-r);
		}
		return res;
	}
	int query(int l, int r) {
		return prefixQuery(r) - prefixQuery(l - 1);
	}
};
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
	int n, q1, q2;
	cin >> n >> q1 >> q2;
	vector<vector<int>> tree(n + 1);
	vector<pair<int, int>> edges(n);
	for (int i = 1; i < n; i++) {
		auto &[u, v] = edges[i];
		cin >> u >> v;
		tree[u].push_back(v);
		tree[v].push_back(u);
	}
	FenwickTree fwt(n + 1);
	vector<vector<int>> up(n + 1);
	vector<int> dist(n + 1), first(n + 1), last(n + 1);
	dist[0] = -1;
	int idx = 1;
	auto dfs = [&] (auto self, int c, int p)->void {
		dist[c] = dist[p] + 1;
		first[c] = idx;
		if (p) {
			int cur = 0, u = p;
			while (true) {
				up[c].push_back(u);
				if (cur >= up[u].size()) {
					break;
				}
				u = up[u][cur];
				cur++;
			}
		}
		for (auto &v : tree[c]) {
			if (v != p) {
				idx++;
				self(self, v, c);
			}
		}
		last[c] = idx;
	};
	dfs(dfs, 1, 0);
	vector<int> info(n + 1, 1), dupe(n + 1, 0);
	vector<bool> on(n + 1, 0);
	auto par = [&] (auto self, int c)->int {
		if (!on[c]) {
			return c;
		}
		int diff = dist[c] - fwt.prefixQuery(first[c]);
		for (int i = 1; i < up[c].size(); i++) {
			if (dist[up[c][i]] - fwt.prefixQuery(first[up[c][i]]) < diff) {
				return self(self, up[c][i - 1]);
			}
		}
		return self(self, up[c].back());
	};
	while (q1--) {
		int x;
		cin >> x;
		auto &[u, v] = edges[x];
		if (dist[u] < dist[v]) {
			swap(u, v);
		}
		if (!on[u]) {
			info[par(par, v)] += info[u] - dupe[u];
			fwt.update(first[u], 1);
			fwt.update(last[u] + 1, -1);
		}
		else {
			info[u] = dupe[u] = info[par(par, u)];
			fwt.update(first[u], -1);
			fwt.update(last[u] + 1, 1);
		}
		on[u] = !on[u];
	}
	while (q2--) {
		int u;
		cin >> u;
		cout << info[par(par, u)] << "\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...