#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 202020
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
pii edges[MAX];
vector<pii> toggle[MAX];
int laston[MAX];
vector<int> adj[MAX];
int ans[MAX];
int vis[MAX];
int num[MAX];
map<int, int> mp[MAX];
int findnxt(int v, int e) { return edges[e].first + edges[e].second - v; }
map<int, int> mpall;
int mpsum;
void bottomup(int x, int p = 0, int isrt = 0) {
mp[x].clear();
mp[x][0] = 1;
int i;
for (auto e : adj[x]) {
int v = findnxt(x, e);
if (vis[v] || v == p) continue;
if (toggle[e].empty()) continue;
bottomup(v, x);
for (i = 0; i < toggle[e].size(); i++) {
int s;
if (i) s = toggle[e][i - 1].second;
else s = -1;
int nxt = toggle[e][i].first;
while (1) {
auto it = mp[v].lower_bound(s);
if (it == mp[v].end()) break;
if (it->first >= nxt) break;
mp[v][nxt] += it->second;
mp[v].erase(it);
}
}
while (mp[v].size() && mp[v].rbegin()->first >= toggle[e].back().second) mp[v].erase(mp[v].rbegin()->first);
if (!isrt) {
if (mp[v].size() > mp[x].size()) swap(mp[v], mp[x]);
for (auto& [a, b] : mp[v]) mp[x][a] += b;
}
}
}
void topdown(int x, int p) {
ans[x] += mpsum;
int i;
for (auto e : adj[x]) {
int v = findnxt(x, e);
if (vis[v] || v == p) continue;
if (toggle[e].empty()) continue;
vector<pii> logv;
for (i = 0; i < toggle[e].size(); i++) {
int s;
if (i) s = toggle[e][i - 1].second;
else s = -1;
int nxt = toggle[e][i].first;
while (1) {
auto it = mpall.lower_bound(s);
if (it == mpall.end()) break;
if (it->first >= nxt) break;
logv.emplace_back(it->first, it->second);
logv.emplace_back(nxt, -it->second);
mpall[nxt] += it->second;
mpall.erase(it);
}
}
while (mpall.size() && mpall.rbegin()->first >= toggle[e].back().second) {
mpsum -= mpall.rbegin()->second;
logv.emplace_back(mpall.rbegin()->first, mpall.rbegin()->second);
mpall.erase(mpall.rbegin()->first);
}
topdown(v, x);
for (auto& [a, b] : logv) mpall[a] += b, mpsum += b;
}
}
void make_num(int x, int p = 0) {
num[x] = 1;
for (auto e : adj[x]) {
int v = findnxt(x, e);
if (v == p || vis[v]) continue;
make_num(v, x);
num[x] += num[v];
}
}
void make_tree(int x) {
make_num(x);
int c = x;
int n = num[x];
while (1) {
int changed = 0;
for (auto e : adj[c]) {
int v = findnxt(c, e);
if (!vis[v] && num[v] < num[c]) {
if (num[v] > n / 2) {
c = v;
changed = 1;
break;
}
}
}
if (!changed) break;
}
bottomup(c, 0, 1);
mpall.clear();
mpsum = 0;
for (auto e : adj[c]) {
int v = findnxt(c, e);
if (vis[v]) continue;
for (auto& [a, b] : mp[v]) if (b) mpall[a] += b, mpsum += b;
}
for (auto& [a, b] : mp[c]) if (b) mpall[a] += b, mpsum += b;
ans[c] += mpsum;
int i;
for (auto e : adj[c]) {
int v = findnxt(c, e);
if (vis[v]) continue;
if (toggle[e].empty()) continue;
for (auto& [a, b] : mp[v]) if (b) mpall[a] -= b, mpsum -= b;
vector<pii> logv;
for (i = 0; i < toggle[e].size(); i++) {
int s;
if (i) s = toggle[e][i - 1].second;
else s = -1;
int nxt = toggle[e][i].first;
while (1) {
auto it = mpall.lower_bound(s);
if (it == mpall.end()) break;
if (it->first >= nxt) break;
logv.emplace_back(it->first, it->second);
logv.emplace_back(nxt, -it->second);
mpall[nxt] += it->second;
mpall.erase(it);
}
}
while (mpall.size() && mpall.rbegin()->first >= toggle[e].back().second) {
mpsum -= mpall.rbegin()->second;
logv.emplace_back(mpall.rbegin()->first, mpall.rbegin()->second);
mpall.erase(mpall.rbegin()->first);
}
topdown(v, c);
for (auto& [a, b] : logv) mpall[a] += b, mpsum += b;
for (auto& [a, b] : mp[v]) if (b) mpall[a] += b, mpsum += b;
}
vis[c] = 1;
for (auto e : adj[c]) {
int v = findnxt(c, e);
if (!vis[v]) make_tree(v);
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int N, M, Q;
cin >> N >> M >> Q;
int i, a, b;
for (i = 1; i < N; i++) {
cin >> a >> b;
edges[i] = pii(a, b);
adj[a].push_back(i);
adj[b].push_back(i);
}
for (i = 1; i <= M; i++) {
cin >> a;
if (laston[a]) {
toggle[a].emplace_back(laston[a], i);
laston[a] = 0;
}
else laston[a] = i;
}
for (i = 1; i < N; i++) if (laston[i]) toggle[i].emplace_back(laston[i], M + 1);
make_tree(1);
vector<int> qs;
while (Q--) {
cin >> a;
qs.push_back(a);
}
for (auto v : qs) cout << ans[v] << ln;
}
Compilation message
synchronization.cpp: In function 'void bottomup(int, int, int)':
synchronization.cpp:36:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for (i = 0; i < toggle[e].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~
synchronization.cpp: In function 'void topdown(int, int)':
synchronization.cpp:64:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (i = 0; i < toggle[e].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~
synchronization.cpp: In function 'void make_tree(int)':
synchronization.cpp:132:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for (i = 0; i < toggle[e].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
19284 KB |
Output is correct |
| 2 |
Correct |
9 ms |
19244 KB |
Output is correct |
| 3 |
Correct |
9 ms |
19332 KB |
Output is correct |
| 4 |
Correct |
11 ms |
19332 KB |
Output is correct |
| 5 |
Correct |
11 ms |
19308 KB |
Output is correct |
| 6 |
Correct |
14 ms |
19468 KB |
Output is correct |
| 7 |
Correct |
57 ms |
20736 KB |
Output is correct |
| 8 |
Correct |
53 ms |
20816 KB |
Output is correct |
| 9 |
Correct |
67 ms |
20712 KB |
Output is correct |
| 10 |
Correct |
811 ms |
34708 KB |
Output is correct |
| 11 |
Correct |
737 ms |
34692 KB |
Output is correct |
| 12 |
Correct |
203 ms |
37836 KB |
Output is correct |
| 13 |
Execution timed out |
8029 ms |
41608 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8021 ms |
46216 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
19284 KB |
Output is correct |
| 2 |
Correct |
10 ms |
19276 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
19244 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
235 ms |
36632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
19284 KB |
Output is correct |
| 2 |
Correct |
11 ms |
19284 KB |
Output is correct |
| 3 |
Correct |
10 ms |
19284 KB |
Output is correct |
| 4 |
Correct |
12 ms |
19268 KB |
Output is correct |
| 5 |
Incorrect |
19 ms |
19496 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
