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;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll N=4e5+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<62);
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()
ll n,x,y,m,q,bit[N],in[N],out[N],ti=1,lca[N][21],cd,ans[N],last[N],B[N];
vector<pll> edge;
vector<ll> v[N];
void DFS(ll nd,ll pa){
lca[nd][0]=pa;
in[nd]=ti++;
ans[nd]=1;
for(ll i=1;i<=20&&lca[nd][i-1];i++)lca[nd][i]=lca[lca[nd][i-1]][i-1];
for(auto i:v[nd]){
if(i==pa)continue;
DFS(i,nd);
}
out[nd]=ti;
}
void mod(ll id,ll dx){
while(id<N)bit[id]+=dx,id+=(id&-id);
}
ll query(ll id){
ll tmp=0;while(id)tmp+=bit[id],id-=(id&-id);return tmp;
}
ll find(ll id){
ll tmp=id;
for(ll i=20;i>=0;i--)if(lca[tmp][i]&&query(in[lca[tmp][i]])==query(in[id]))tmp=lca[tmp][i];
return tmp;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m>>q;
REP(i,n-1){
cin>>x>>y;
edge.pb(mp(x,y));
v[x].pb(y);v[y].pb(x);
}
DFS(1,0);
REP1(i,n)mod(in[i],-1),mod(out[i],1);
REP(i,m){
cin>>cd;
y=edge[cd-1].Y;x=edge[cd-1].X;
if(lca[y][0]==x)swap(x,y);
if(B[cd-1]){
ans[x]=last[x]=ans[find(y)];
mod(in[x],-1),mod(out[x],1);
}else{
ans[find(y)]+=ans[x]-last[x];
mod(in[x],1),mod(out[x],-1);
}
B[cd-1]=1-B[cd-1];
}
while(q--)cin>>x,cout<<ans[find(x)]<<"\n";
return 0;
}
# | 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... |