#include "bits/stdc++.h"
using namespace std;
int l[100010], r[100010];
int n;
int par[100010];
vector <int> g[100010];
int sub[100010];
bool del[100010];
int rt[100010];
bool vis[100010];
int sz[100010];
int last[100010];
vector <int> aux[100010];
void dfs(int x, int p) {
sub[x] = 1;
for(auto e : g[x]) {
int i = l[e] ^ r[e] ^ x;
if(e != p && !del[i]) {
dfs(i, e);
sub[x] += sub[i];
}
}
}
int centroid(int x, int p, int range) {
for(auto e : g[x]) {
int i = l[e] ^ r[e] ^ x;
if(e != p && sub[i] > range && !del[i]) {
return centroid(i, e, range);
}
}
return x;
}
vector <int> nodes;
void prec(int x, int p, int src) {
par[x] = p;
rt[x] = src;
nodes.push_back(x);
for(auto e : g[x]) {
int i = l[e] ^ r[e] ^ x;
if(e != p && !del[i]) {
prec(i, e, src);
}
}
}
struct data {
int r, cnt, pos;
data (int r, int cnt, int pos) : r(r), cnt(cnt), pos(pos) {}
data () {}
bool operator < (data f) const {
return pos < f.pos;
}
};
bool cmp(int i, int j) {
return last[i] < last[j];
}
int ans[100010];
int sum[100010];
int nxt[100010];
int head[100010];
int pos[100010];
int rev[100010];
set <int> s[100010];
void hld(int x, int p) {
sub[x] = 1;
nxt[x] = -1;
for(auto e : g[x]) {
int i = l[e] ^ r[e] ^ x;
if(e != p) {
hld(i, e);
sub[x] += sub[i];
if(nxt[x] == -1 || sub[nxt[x]] < sub[i]) {
nxt[x] = i;
}
}
}
}
int root(int x) {
while(true) {
int h = head[x];
if(s[h].empty() || *s[h].begin() > pos[x]) {
x = h;
x ^= l[par[x]] ^ r[par[x]];
} else {
return rev[*(--s[h].upper_bound(pos[x]))];
}
}
return 0;
}
void invert(int e) {
int u;
if(par[l[e]] == e) u = l[e];
else u = r[e];
vis[e] ^= 1;
if(vis[e]) {
s[head[u]].erase(pos[u]);
} else {
s[head[u]].insert(pos[u]);
}
}
// int invert(int e) {
// vis[e] ^= 1;
// }
// int root(int u) {
// while(vis[par[u]]) {
// u ^= l[par[u]] ^ r[par[u]];
// }
// return u;
// }
void solve(int x, vector <int> Q) {
dfs(x, 0);
x = centroid(x, 0, sub[x] / 2);
del[x] = true;
nodes.clear();
par[x] = 0;
for(auto e : g[x]) {
int i = l[e] ^ r[e] ^ x;
if(del[i]) continue;
prec(i, e, i);
sum[i] = 0;
aux[i].clear();
}
hld(x, 0);
nodes.push_back(x);
int idx = 0;
for(int i : nodes) {
int p = l[par[i]] ^ r[par[i]] ^ i;
if(i == x || nxt[p] != i) {
for(int j = i; j != -1; j = nxt[j]) {
head[j] = i;
pos[j] = ++idx;
rev[idx] = j;
}
}
}
for(auto i : nodes) {
vis[par[i]] = 0;
sz[i] = 1;
s[i].clear();
}
for(auto i : nodes) {
s[head[i]].insert(pos[i]);
}
nodes.pop_back();
vector <data> cont;
sum[x] = 0;
cont.emplace_back(x, 1, -1);
for(int h = 0; h < Q.size(); h++) {
int e = Q[h];
int u;
if(par[l[e]] == e) u = l[e];
else u = r[e];
if(!vis[e]) {
invert(e);
if(root(u) == x) {
if (sz[u] > 0) {
cont.emplace_back(rt[u], sz[u], h);
}
sz[u] = 0;
} else {
sz[root(u)] += sz[u];
sz[u] = 0;
}
} else {
invert(e);
}
}
sort(cont.begin(), cont.end());
for(auto i : cont) {
ans[x] += i.cnt;
}
for(auto i : nodes) {
if(vis[par[i]]) {
invert(par[i]);
}
last[i] = INT_MIN;
}
for(int h = 0; h < Q.size(); h++) {
int e = Q[h];
int u;
if(par[l[e]] == e) u = l[e];
else u = r[e];
last[x] = h;
if(vis[e]) {
last[u] = last[root(u)];
invert(e);
} else {
invert(e);
}
}
last[x] = Q.size();
for(auto i : nodes) {
last[i] = last[root(i)];
}
sort(nodes.begin(), nodes.end(), cmp);
int pt = 0;
int tot = 0;
for(int i : nodes) {
while(pt < cont.size() && cont[pt].pos < last[i]) {
sum[cont[pt].r] += cont[pt].cnt;
tot += cont[pt].cnt;
++pt;
}
ans[i] += tot - sum[rt[i]];
}
for(int h = 0; h < Q.size(); h++) {
int e = Q[h];
int u;
if(par[l[e]] == e) u = l[e];
else u = r[e];
if(rt[u] != u) {
aux[rt[u]].push_back(e);
}
}
for(auto e : g[x]) {
int i = l[e] ^ r[e] ^ x;
if(del[i]) continue;
solve(i, aux[i]);
}
}
int main(int argc, char const *argv[])
{
int m, qr;
scanf("%d %d %d", &n, &m, &qr);
for(int i = 1; i < n; i++) {
scanf("%d %d", l + i, r + i);
g[l[i]].push_back(i);
g[r[i]].push_back(i);
}
vector <int> Q;
for(int i = 1; i <= m; i++) {
int x;
scanf("%d", &x);
Q.push_back(x);
}
solve(1, Q);
for(int i = 1; i <= qr; i++) {
int u;
scanf("%d", &u);
printf("%d\n", ans[u]);
}
return 0;
}
Compilation message
synchronization.cpp: In function 'void solve(int, std::vector<int>)':
synchronization.cpp:159:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < Q.size(); h++) {
~~^~~~~~~~~~
synchronization.cpp:190:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < Q.size(); h++) {
~~^~~~~~~~~~
synchronization.cpp:213:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(pt < cont.size() && cont[pt].pos < last[i]) {
~~~^~~~~~~~~~~~~
synchronization.cpp:220:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < Q.size(); h++) {
~~^~~~~~~~~~
synchronization.cpp: In function 'int main(int, const char**)':
synchronization.cpp:240:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &m, &qr);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:243:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", l + i, r + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:250:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
synchronization.cpp:257:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &u);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 3 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 4 |
Correct |
9 ms |
9728 KB |
Output is correct |
| 5 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 6 |
Correct |
26 ms |
9856 KB |
Output is correct |
| 7 |
Correct |
4600 ms |
12256 KB |
Output is correct |
| 8 |
Correct |
4724 ms |
12248 KB |
Output is correct |
| 9 |
Correct |
4686 ms |
12240 KB |
Output is correct |
| 10 |
Execution timed out |
8023 ms |
26700 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8098 ms |
30232 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
9 ms |
9728 KB |
Output is correct |
| 3 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 4 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 5 |
Correct |
9 ms |
9728 KB |
Output is correct |
| 6 |
Correct |
33 ms |
10112 KB |
Output is correct |
| 7 |
Correct |
1938 ms |
15080 KB |
Output is correct |
| 8 |
Execution timed out |
8034 ms |
33828 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8026 ms |
33464 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9752 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 3 |
Correct |
9 ms |
9728 KB |
Output is correct |
| 4 |
Correct |
11 ms |
9856 KB |
Output is correct |
| 5 |
Correct |
27 ms |
9984 KB |
Output is correct |
| 6 |
Correct |
4690 ms |
12412 KB |
Output is correct |
| 7 |
Execution timed out |
8068 ms |
26452 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
