Submission #59894

#TimeUsernameProblemLanguageResultExecution timeMemory
59894gusfringSynchronization (JOI13_synchronization)C++14
100 / 100
595 ms46676 KiB
#include <bits/stdc++.h>
using namespace std;
 
const int N = 100005;
 
int n, m, q;
int cnt;
int res[N], lst[N];
int h[N], st[N], ed[N], pos[N];
int from[N], to[N];
int it[4 * N];
bool type[N];
vector<int> G[N];
 
void dfs(int u, int p) {
	st[u] = ++cnt, pos[cnt] = u;
	for (auto v : G[u]) {
		if (v == p) continue;
		h[v] = h[u] + 1, dfs(v, u);
	}
	ed[u] = cnt;
}
 
void build(int i, int l, int r) {
	if (l == r) {
		it[i] = ed[pos[l]]; return;
	}
	int mid = (l + r) >> 1;
	build(i << 1, l, mid), build(i << 1 | 1, mid + 1, r);
	it[i] = max(it[i << 1], it[i << 1 | 1]);
}
 
void upd(int i, int l, int r, int p, int x) {
	if (l == r) {
		it[i] = x; return;
	}
	int mid = (l + r) >> 1;
	if (mid >= p) upd(i << 1, l, mid, p, x);
	else upd(i << 1 | 1, mid + 1, r, p, x);
	it[i] = max(it[i << 1], it[i << 1 | 1]);
}
 
int find(int i, int l, int r, int u, int v) {
	if (l > u || it[i] < v) return -1;
	if (l == r) return l;
	int mid = (l + r) >> 1;
	int res = find(i << 1 | 1, mid + 1, r, u, v);
	if (res != -1) return res;
	return find(i << 1, l, mid, u, v);
}
 
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> q;
	for (int i = 1; i < n; ++i) {
		cin >> from[i] >> to[i];
		G[from[i]].push_back(to[i]);
		G[to[i]].push_back(from[i]);
	}
	dfs(1, 1);
	for (int i = 1; i <= n; ++i) res[i] = 1;
	build(1, 1, n);
	for (int i = 1; i < n; ++i) {
		if (h[from[i]] > h[to[i]]) swap(from[i], to[i]);
	}
	for (int i = 1; i <= m; ++i) {
		int x; cin >> x;
		if (!type[x]) {
			res[pos[find(1, 1, n, st[from[x]], ed[from[x]])]] += res[to[x]] - lst[x];
			upd(1, 1, n, st[to[x]], 0);
		}
		else {
			res[to[x]] = lst[x] = res[pos[find(1, 1, n, st[from[x]], ed[from[x]])]];
			upd(1, 1, n, st[to[x]], ed[to[x]]);
		}
		type[x] ^= 1;
	}
	for (int i = 1; i <= q; ++i) {
		int x; cin >> x; cout << res[pos[find(1, 1, n, st[x], ed[x])]] << '\n';
	}
}
#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...