This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int nx=1e5+5, kx=17;
int n, m, q, u[nx], v[nx], pa[nx][kx], lvl[nx], on[nx], dp[nx], l[nx], in[nx], out[nx], t, x, vs[nx];
vector<pair<int, int>> d[nx];
void dfs(int u, int p)
{
lvl[u]=lvl[p]+1; pa[u][0]=p; dp[u]=1; in[u]=++t;
for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
for (auto [v, idx]:d[u]) if (v!=p) dfs(v, u);
out[u]=t;
}
struct fenwick
{
int d[nx];
void add(int idx, int vl)
{
for (int i=idx; i<nx; i+=(i&-i)) d[i]+=vl;
}
int find(int idx)
{
int res=0;
for (int i=idx; i>0; i-=(i&-i)) res+=d[i];
return res;
}
} f;
int findrt(int u)
{
for (int i=kx-1; i>=0; i--) if (f.find(u)-f.find(pa[u][i])==lvl[u]-lvl[pa[u][i]]) u=pa[u][i];
return u;
}
void dfs2(int u, int vl)
{
vs[u]=1;
dp[u]=vl;
for (auto [v, idx]:d[u]) if (on[idx]&&v!=pa[u][0]) dfs2(v, vl);
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>m>>q;
for (int i=1; i<n; i++) cin>>u[i]>>v[i], d[u[i]].push_back({v[i], i}), d[v[i]].push_back({u[i], i});
dfs(1, 1);
for (int i=1; i<=m; i++)
{
cin>>x;
if (lvl[u[x]]>lvl[v[x]]) swap(u[x], v[x]);
if (on[x])
{
l[v[x]]=dp[v[x]]=dp[findrt(v[x])];
f.add(in[v[x]], -1);
f.add(out[v[x]]+1, 1);
}
else
{
dp[findrt(u[x])]+=dp[v[x]]-l[v[x]];
f.add(in[v[x]], 1);
f.add(out[v[x]]+1, -1);
}
on[x]=!on[x];
}
for (int i=1; i<=n; i++) if (!vs[i]) dfs2(findrt(i), dp[findrt(i)]);
while (q--) cin>>x, cout<<dp[x]<<'\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... |