#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int N=6767;
bitset<N> bt[MAXN];
vector<int> vi[MAXN*8];
pair<int,int> edge[MAXN];
int pos[MAXN],ans[MAXN],dsu[MAXN],cnt[MAXN];
stack< pair<int,int> > st;
int root(int i)
{
if(!dsu[i]) return i;
return root(dsu[i]);
}
void merge(int i,int j,int p)
{
if(cnt[i]<cnt[j]) swap(i,j);
dsu[j]=i,cnt[i]+=cnt[j],bt[i]|=bt[j];
st.push({i,j});
}
void rollback()
{
int l=st.top().first,r=st.top().second;
st.pop();
dsu[r]=0,cnt[l]-=cnt[r],bt[r]=bt[l];
}
void update(int l,int r,int u,int v,int val,int pos)
{
if(v<l||r<u) return ;
if(u<=l&&r<=v)
{
vi[pos].push_back(val);
return ;
}
int mid=(l+r)/2;
update(l,mid,u,v,val,pos*2);
update(mid+1,r,u,v,val,pos*2+1);
}
void dnc(int l,int r,int pos)
{
for(auto v:vi[pos]) merge(edge[v].first,edge[v].second,v);
if(l!=r)
{
int mid=(l+r)/2;
dnc(l,mid,pos*2);
dnc(mid+1,r,pos*2+1);
}
for(auto v:vi[pos]) rollback();
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m,q;
cin>>n>>m>>q;
for(int i=1;i<n;i++) cin>>edge[i].first>>edge[i].second;
for(int i=1;i<=m;i++)
{
int res;
cin>>res;
if(!pos[res]) pos[res]=i;
else
{
update(1,m,pos[res],i-1,res,1);
pos[res]=0;
}
}
for(int i=1;i<n;i++) if(pos[i]) update(1,m,pos[i],m,i,1);
int pre=1;
for(int i=1;i<=n;i++) cnt[i]=1;
for(int i=1;i<=n;i++) if(i%N==0||i==n)
{
for(int j=pre;j<=i;j++) bt[j][(j-1)%N]=1;
pre=i+1;
dnc(1,m,1);
for(int j=1;j<=n;j++) ans[j]+=bt[j].count(),bt[j]=0;
}
while(q--)
{
int res;
cin>>res;
cout<<ans[res]<<"\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... |