#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 2e5 + 7;
int in[mxN], out[mxN], num, n, m, q, u[mxN], v[mxN], bit[mxN], par[mxN][30], mem[mxN], ans[mxN];
vector<int> w[mxN];
void Upd(int j, int val)
{
while (j <= n)
{
bit[j] += val;
j += j & (-j);
}
}
int Get(int j)
{
int res = 0;
while (j > 0)
{
res += bit[j];
j -= j & (-j);
}
return res;
}
void DFS(int j)
{
in[j] = ++num;
for (int i = 1; i <= 20; i++)
par[j][i] = par[par[j][i - 1]][i - 1];
for (int i : w[j])
{
if (in[i])
continue;
par[i][0] = j;
DFS(i);
}
out[j] = num + 1;
Upd(in[j], 1);
Upd(out[j], -1);
}
int Find(int j)
{
int tmp = Get(in[j]);
for (int i = 20; i >= 0; i--)
{
if (Get(in[par[j][i]]) == tmp)
j = par[j][i];
}
return j;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen(task".INP", "r", stdin);
//freopen(task".OUT", "w", stdout);
cin >> n >> m >> q;
for (int i = 1; i < n; i++)
{
cin >> u[i] >> v[i];
w[u[i]].push_back(v[i]);
w[v[i]].push_back(u[i]);
}
DFS(1);
for (int i = 1; i <= n; i++)
ans[i] = 1;
for (int i = 1; i < n; i++)
{
if (par[u[i]][0] == v[i])
swap(u[i], v[i]);
}
for (int i = 1; i <= m; i++)
{
int id;
cin >> id;
int root = Find(u[id]);
if (mem[id] == -1)
{
Upd(in[v[id]], 1);
Upd(out[v[id]], -1);
mem[id] = ans[v[id]] = ans[root];
}
else
{
Upd(in[v[id]], -1);
Upd(out[v[id]], 1);
ans[v[id]] = ans[root] = ans[v[id]] + ans[root] - mem[id];
mem[id] = -1;
}
}
for (int i = 1; i <= q; i++)
{
int tmp;
cin >> tmp;
cout << ans[Find(tmp)] << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |