// Code by Parsa Eslami
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define bit(i,j) ((j>>i)&1)
#define minm(x,y) x=min(x,y)
#define maxm(x,y) x=max(x,y)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n'
#define wtf cout<<"WHAT THE FUCK!\n"
#define dmid int mid=(r+l)/2
#define lc 2*id
#define rc 2*id+1
using namespace std;
const int N=2e5+4;
int S[N],seg[2][4*N],lazy[4*N];
vector<pair<int,pii>> adj[N];
vector<int> vc[N];
bool hide[N];
vector<pii> his[N];
int ans[N];
int n,m;
void undo(int x){
for(pii w:his[x]){
if(w.F<0) lazy[-w.F]=w.S;
else seg[w.F&1][w.F/2]=w.S;
}
}
void _(int id,int x,int h,bool b){
if(h!=-1) his[h].pb({2*id+b,seg[b][id]});
seg[b][id]=x;
}
void _(int id,int x,int h){
if(h!=-1) his[h].pb({-id,lazy[id]});
lazy[id]=x;
}
void shift(int id,int h){
if(!lazy[id]) return;
_(lc,lazy[id],h,1);
_(lc,lazy[id],h,0);
_(rc,lazy[id],h,1);
_(rc,lazy[id],h,0);
_(lc,lazy[id],h);
_(rc,lazy[id],h);
_(id,0,h);
}
int bs0(int id,int l,int r,int x,int h){// <=x
if(seg[0][1]>x) return 0;
if(l+1==r) return l;
dmid;
shift(id,h);
if(seg[0][rc]<=x) return bs0(rc,mid,r,x,h);
else return bs0(lc,l,mid,x,h);
}
int bs1(int id,int l,int r,int x,int h){// >=x
if(seg[1][1]<x) return m+1;
if(l+1==r) return l;
dmid;
shift(id,h);
if(seg[1][lc]>=x) return bs1(lc,l,mid,x,h);
else return bs1(rc,mid,r,x,h);
}
void upd(int id,int l,int r,int st,int en,int x,int h){
if(st>=r||en<=l) return;
if(st<=l&&en>=r){
_(id,x,h,0);
_(id,x,h,1);
_(id,x,h);
return;
}
dmid;
shift(id,h);
upd(lc,l,mid,st,en,x,h);
upd(rc,mid,r,st,en,x,h);
_(id,seg[0][lc],h,0);
_(id,seg[1][rc],h,1);
}
void plant(int v,int p){
S[v]=SZ(adj[v]);
FOR(i,0,SZ(adj[v])-1) if((i==0||adj[v][i].F!=adj[v][i-1].F)&&adj[v][i].F!=p&&!hide[adj[v][i].F]){
int u=adj[v][i].F;
plant(u,v);
S[v]+=S[u];
}
}
int find_centroid(int v,int p,int _n){
FOR(i,0,SZ(adj[v])-1) if((i==0||adj[v][i].F!=adj[v][i-1].F)&&!hide[adj[v][i].F]&&adj[v][i].F!=p&&2*S[adj[v][i].F]>_n) return find_centroid(adj[v][i].F,v,_n);
return v;
}
void dfs1(int v,int p,int h,int a1,int a2){
int WW=bs0(1,1,m+1,m,h);
if(WW!=0&&a1!=a2) ans[v]-=(upper_bound(all(vc[a1]),WW)-vc[a1].begin());
if(WW!=0) ans[v]+=(upper_bound(all(vc[a2]),WW)-vc[a2].begin());
FOR(i,0,SZ(adj[v])-1) if(adj[v][i].F!=p&&!hide[adj[v][i].F]){
vector<pii> b;
int u=adj[v][i].F;
b.pb(adj[v][i].S);
while(i!=SZ(adj[v])-1&&adj[v][i+1].F==u){
i++;
b.pb(adj[v][i].S);
}
FOR(ii,0,SZ(b)-2){
int l=bs1(1,1,m+1,b[ii].S+1,h+1);
int r=bs0(1,1,m+1,b[ii+1].F-1,h+1)+1;
if(r>l) upd(1,1,m+1,l,r,b[ii+1].F,h+1);
}
int x=bs0(1,1,m+1,b[0].F-1,h+1)+1;
if(x>1) upd(1,1,m+1,1,x,b[0].F,h+1);
x=bs1(1,1,m+1,b.back().S+1,h+1);
if(x<m+1) upd(1,1,m+1,x,m+1,m+1,h+1);
if(a1==a2) dfs1(u,v,h+1,u,v);
else dfs1(u,v,h+1,a1,a2);
undo(h+1);
}
}
void dfs2(int v,int p,int h,int a1,int a2){
//cout<<v<<" ";
int WW=m+1-bs0(1,1,m+1,m,h);
if(a1!=a2) vc[a1].pb(WW);
vc[a2].pb(WW);
FOR(i,0,SZ(adj[v])-1) if(adj[v][i].F!=p&&!hide[adj[v][i].F]){
vector<pii> b;
int u=adj[v][i].F;
b.pb(adj[v][i].S);
while(i!=SZ(adj[v])-1&&adj[v][i+1].F==u){
i++;
b.pb(adj[v][i].S);
}
FOR(ii,0,SZ(b)-1) b[ii]={m+1-b[ii].S,m+1-b[ii].F};
reverse(all(b));
FOR(ii,0,SZ(b)-2){
int l=bs1(1,1,m+1,b[ii].S+1,h+1);
int r=bs0(1,1,m+1,b[ii+1].F-1,h+1)+1;
if(r>l) upd(1,1,m+1,l,r,b[ii+1].F,h+1);
}
int x=bs0(1,1,m+1,b[0].F-1,h+1)+1;
if(x>1) upd(1,1,m+1,1,x,b[0].F,h+1);
x=bs1(1,1,m+1,b.back().S+1,h+1);
if(x<m+1) upd(1,1,m+1,x,m+1,m+1,h+1);
if(a1==a2) dfs2(u,v,h+1,u,v);
else dfs2(u,v,h+1,a1,a2);
undo(h+1);
}
}
void decompose(int v){
plant(v,v);
v=find_centroid(v,v,S[v]);
dfs2(v,v,0,v,v);
/*FOR(i,0,SZ(adj[v])-1) if(i==0||adj[v][i].F!=adj[v][i-1].F){
int u=adj[v][i].F;
if(!hide[u]) dfs2(u,u,0,u,v);
}*/
sort(all(vc[v]));
FOR(i,0,SZ(adj[v])-1) if(i==0||adj[v][i].F!=adj[v][i-1].F){
int u=adj[v][i].F;
if(!hide[u]) sort(all(vc[u]));
}
/*FOR(i,0,SZ(adj[v])-1) if(i==0||adj[v][i].F!=adj[v][i-1].F){
int u=adj[v][i].F;
if(!hide[u]) dfs1(u,u,0,u,v);
}*/
dfs1(v,v,0,v,v);
/*cout<<"#"<<v<<'\n';
FOR(i,1,2){
for(int wu:vc[i]) cout<<wu<<" ";
cout<<'\n';
}*/
hide[v]=1;
vc[v].clear();
vc[v].shrink_to_fit();
FOR(i,0,SZ(adj[v])-1) if(i==0||adj[v][i].F!=adj[v][i-1].F){
int u=adj[v][i].F;
if(!hide[u]){
vc[u].clear();
vc[u].shrink_to_fit();
decompose(u);
}
}
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int q; cin>>n>>m>>q;
pii E[n];
FOR(i,1,n-1) cin>>E[i].F>>E[i].S;
map<int,int> mp;
FOR(i,1,m){
int w; cin>>w;
if(mp[w]){
int l=mp[w];
int r=i;
mp[w]=0;
int u=E[w].F;
int v=E[w].S;
adj[u].pb({v,{l,r}});
adj[v].pb({u,{l,r}});
}else mp[w]=i;
}
for(pii x0:mp) if(x0.S!=0){
int l=x0.S;
int r=m;
int u=E[x0.F].F;
int v=E[x0.F].S;
adj[u].pb({v,{l,r}});
adj[v].pb({u,{l,r}});
}
FOR(i,1,m) upd(1,1,m+1,i,i+1,i,-1);
FOR(i,1,n) sort(all(adj[i]));
FOR(i,1,n) if(!hide[i]) decompose(i);
while(q--){
int v; cin>>v; cout<<ans[v]<<'\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
10 ms |
14432 KB |
Output is correct |
| 4 |
Correct |
9 ms |
14448 KB |
Output is correct |
| 5 |
Incorrect |
15 ms |
14884 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8058 ms |
80080 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8061 ms |
44976 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
14412 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
