#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 5;
int n;
int parent[maxn], h[maxn], sz[maxn], pos[maxn], st[maxn], ft[maxn], up[maxn];
vector<int> t[maxn];
bitset<maxn> bs[maxn];
int Time = 0;
int seg[4 * maxn];
pair<int,int> edge[2 * maxn];
bool black[maxn];
int get(int id, int L, int R, int l, int r){
if (r <= L or R <= l or seg[id] == 1)
return -1;
if (L + 1 == R)
return L;
int mid = (L + R) >> 1;
return max(get(2 * id + 0, L, mid, l, r), get(2 * id + 1, mid, R, l, r));
}
void add(int id, int L, int R, int idx, bool val){
if (idx < L or R <= idx)
return;
if (L + 1 == R){
seg[id] = val;
return;
}
int mid = (L + R) >> 1;
add(2 * id + 0, L, mid, idx, val);
add(2 * id + 1, mid, R, idx, val);
seg[id] = min(seg[2 * id + 0], seg[2 * id + 1]);
}
int get_par(int v){
while (v != 0){
int me = get(1, 0, n, st[up[v]], st[v] + 1);
if (me != -1)
return pos[me];
v = parent[up[v]];
}
return v;
}
void add(int v, int par){
int u = get_par(par);
bs[u] |= bs[v];
add(1, 0, n, st[v], 1);
}
void del(int v, int par){
int u = get_par(par);
bs[v] = bs[u];
add(1, 0, n, st[v], 0);
}
bool cmpsz(int v, int u){ return sz[v] < sz[u]; }
void dfs(int v, int par = -1){
st[v] = Time;
pos[Time ++] = v;
sort(t[v].begin(), t[v].end(), cmpsz);
if (par != -1) //t[v].back() = par
t[v].pop_back();
reverse(t[v].begin(), t[v].end());
bool heavy = true;
for (auto u : t[v]){
if (heavy == true)
up[u] = up[v];
else
up[u] = u;
dfs(u, v);
heavy = false;
}
ft[v] = Time;
}
void dfs_sz(int v, int par = -1){
parent[v] = par;
sz[v] = 1;
for (auto u : t[v])
if (u != par)
h[u] = h[v] + 1, dfs_sz(u, v), sz[v] += sz[u];
}
int main(){
ios_base::sync_with_stdio (false);
int m, q;
cin >> n >> m >> q;
for (int i = 0; i < n - 1; i++){
int v, u;
cin >> v >> u;
v --, u --;
t[v].push_back(u);
t[u].push_back(v);
edge[i] = {v, u};
}
dfs_sz(0);
dfs(0);
for (int i = 0; i < n; i++)
bs[i][i] = 1;
for (int i = 0; i < m; i++){
int idx;
cin >> idx;
idx --;
int v = edge[idx].first, u = edge[idx].second;
if (h[v] < h[u])
swap(v, u);
if (black[v])
del(v, u);
else
add(v, u);
black[v] ^= 1;
}
for (int i = 0; i < q; i++){
int v;
cin >> v;
v --;
v = get_par(v);
cout << bs[v].count() << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
