#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
struct yal{
vector<pair<int,int>>w,dp,link;
int u,v;
int getad(int fu){
int ret=(u^v^fu);
return ret;
}
};
char c;
void fastscan(int &nu)
{
nu = 0;
c = getchar();
for (; (c>47 && c<58); c=getchar())
nu = nu *10 + c - 48;
}
yal alled[maxn];
vector<int>adj[maxn],fake,bal[maxn],khod[maxn];
int fn,n,m,res[maxn],vis[maxn],sz[maxn],azb[maxn],high[maxn],timea,q,par[maxn];
pair<int,int>stf[maxn];
int kaf=(1<<18);
struct segment{
int seg[(1<<19)];
vector<pair<int,int>>v;
void back(int len){
while((int)v.size()>len){
seg[v.back().first]=v.back().second;
v.pop_back();
}
}
void upd(int i,int l,int r,int tl,int tr,int w){
if(l>r||l>tr||r<tl||tl>tr){
return ;
}
if(l>=tl&&r<=tr){
v.push_back(make_pair(i,seg[i]));
seg[i]=w;
return ;
}
int m=(l+r)>>1;
upd((i<<1),l,m,tl,tr,w);
upd((i<<1)^1,m+1,r,tl,tr,w);
return ;
}
int pors(int i){
if(i==0){
return 0;
}
int ret=pors((i>>1));
if(high[seg[i]]>high[ret]){
ret=seg[i];
}
return ret;
}
}seg;
void dfs(int u,int para=0,int az=0){
fake.push_back(u);
high[u]=high[para]+1;
azb[u]=az;
sz[u]=1;
if(para==0){
high[u]=1;
timea=0;
}
else{
sz[u]+=(int)alled[par[u]].w.size();
}
timea++;
stf[u].first=timea;
for(auto xx:adj[u]){
int x=alled[xx].getad(u);
if(vis[x]==1||x==para){
continue;
}
par[x]=xx;
if(para==0){
bal[x].clear();
dfs(x,u,x);
}
else{
dfs(x,u,az);
}
sz[u]+=sz[x];
}
stf[u].second=timea;
}
int finds(int u,int para=0){
for(auto xx:adj[u]){
int x=alled[xx].getad(u);
if(vis[x]==0&&x!=para&&sz[x]*2>fn){
return finds(x,u);
}
}
return u;
}
void calalllink(int u,int para=0){
int fl=(int)seg.v.size();
if(para==0){
seg.upd(1,0,kaf-1,1,m+5,u);
}
else{
alled[par[u]].link.clear();
alled[par[u]].link.resize((int)alled[par[u]].w.size());
for(int i=0;i<(int)alled[par[u]].w.size();i++){
alled[par[u]].link[i].first=seg.pors(kaf+alled[par[u]].w[i].first);
alled[par[u]].link[i].second=seg.pors(kaf+alled[par[u]].w[i].second);
// cout<<u<<" "<<alled[par[u]].link[i].first<<" "<<alled[par[u]].link[i].second<<" "<<alled[par[u]].w[i].first<<" "<<alled[par[u]].w[i].second<<"\n";
}
if((int)alled[par[u]].w.size()>0){
seg.upd(1,0,kaf-1,1,alled[par[u]].w[0].first-1,u);
seg.upd(1,0,kaf-1,alled[par[u]].w.back().second+1,m+5,u);
for(int i=1;i<(int)alled[par[u]].w.size();i++){
seg.upd(1,0,kaf-1,alled[par[u]].w[i-1].second+1,alled[par[u]].w[i].first-1,u);
}
}
else{
seg.upd(1,0,kaf-1,1,m+5,u);
}
}
for(auto xx:adj[u]){
int x=alled[xx].getad(u);
if(vis[x]==0&&x!=para){
calalllink(x,u);
}
}
seg.back(fl);
}
void solve(int u){
dfs(u);
fake.clear();
fn=sz[u];
int v=finds(u);
fake.clear();
dfs(v);
calalllink(v);
for(auto x:fake){
if(x==v){
khod[v].push_back(0);
continue;
}
for(int i=0;i<(int)alled[par[x]].w.size();i++){
int linky1=alled[par[x]].link[i].first;
int p=lower_bound(alled[par[linky1]].w.begin(),alled[par[linky1]].w.end(),make_pair(alled[par[x]].w[i].first,-1))-alled[par[linky1]].w.begin();
if(linky1==v){
alled[par[x]].dp[i].first=alled[par[x]].w[i].first;
}
else if(p==(int)alled[par[linky1]].w.size()){
alled[par[x]].dp[i].first=m+10;
}
else{
alled[par[x]].dp[i].first=alled[par[linky1]].dp[p].first;
}
int linky2=alled[par[x]].link[i].second;
p=lower_bound(alled[par[linky2]].w.begin(),alled[par[linky2]].w.end(),make_pair(alled[par[x]].w[i].second,-1))-alled[par[linky2]].w.begin();
p--;
if(linky2==v){
alled[par[x]].dp[i].second=alled[par[x]].w[i].second;
}
else if(p<0){
alled[par[x]].dp[i].second=-1;
}
else{
alled[par[x]].dp[i].second=alled[par[linky2]].dp[p].second;
}
}
if(alled[par[x]].w.size()==0){
continue;
}
int ff=alled[par[x]].dp[0].first;
if(ff>m+2){
continue;
}
khod[v].push_back(ff);
bal[azb[x]].push_back(ff);
}
sort(khod[v].begin(),khod[v].end());
for(auto xx:adj[v]){
int x=alled[xx].getad(v);
if(vis[x]==0){
sort(bal[x].begin(),bal[x].end());
}
}
for(auto x:fake){
if(x==v){
res[x]+=khod[v].size();
continue;
}
if((int)alled[par[x]].w.size()==0){
continue;
}
int ff=alled[par[x]].dp.back().second;
int p=upper_bound(khod[v].begin(),khod[v].end(),ff)-khod[v].begin();
p--;
res[x]+=p+1;
p=upper_bound(bal[azb[x]].begin(),bal[azb[x]].end(),ff)-bal[azb[x]].begin();
p--;
res[x]-=p+1;
}
vis[v]=1;
for(auto xx:adj[v]){
int x=alled[xx].getad(v);
if(vis[x]==0){
solve(x);
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("inp.txt","r",stdin);
// freopen("out.txt","w",stdout);
fastscan(n);
fastscan(m);
fastscan(q);
// cin>>n>>m>>q;
for(int i=1;i<=n-1;i++){
fastscan(alled[i].u);fastscan(alled[i].v);
//cin>>alled[i].u>>alled[i].v;
adj[alled[i].u].push_back(i);
adj[alled[i].v].push_back(i);
}
for(int i=1;i<=m;i++){
int u;
fastscan(u);
//cin>>u;
if((int)alled[u].w.size()==0||alled[u].w.back().second!=-1){
alled[u].w.push_back(make_pair(i,-1));
}
else{
alled[u].w.back().second=i;
}
}
for(int i=1;i<n;i++){
if((int)alled[i].w.size()>0&&alled[i].w.back().second==-1){
alled[i].w.back().second=m+1;
}
alled[i].dp.resize((int)alled[i].w.size());
}
solve(1);
for(int i=0;i<q;i++){
int u;
//cin>>u;
fastscan(u);
cout<<res[u]<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
15188 KB |
Output is correct |
| 2 |
Correct |
7 ms |
15256 KB |
Output is correct |
| 3 |
Correct |
8 ms |
15224 KB |
Output is correct |
| 4 |
Correct |
8 ms |
15188 KB |
Output is correct |
| 5 |
Correct |
7 ms |
15188 KB |
Output is correct |
| 6 |
Correct |
13 ms |
15444 KB |
Output is correct |
| 7 |
Correct |
87 ms |
17512 KB |
Output is correct |
| 8 |
Correct |
86 ms |
17484 KB |
Output is correct |
| 9 |
Correct |
100 ms |
17612 KB |
Output is correct |
| 10 |
Correct |
1355 ms |
38652 KB |
Output is correct |
| 11 |
Correct |
1480 ms |
38572 KB |
Output is correct |
| 12 |
Correct |
1672 ms |
58588 KB |
Output is correct |
| 13 |
Correct |
225 ms |
38212 KB |
Output is correct |
| 14 |
Correct |
1125 ms |
44200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
735 ms |
56312 KB |
Output is correct |
| 2 |
Correct |
680 ms |
55496 KB |
Output is correct |
| 3 |
Correct |
1124 ms |
68264 KB |
Output is correct |
| 4 |
Correct |
1096 ms |
67612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
15188 KB |
Output is correct |
| 2 |
Correct |
8 ms |
15188 KB |
Output is correct |
| 3 |
Correct |
10 ms |
15188 KB |
Output is correct |
| 4 |
Correct |
8 ms |
15228 KB |
Output is correct |
| 5 |
Correct |
8 ms |
15188 KB |
Output is correct |
| 6 |
Correct |
17 ms |
15704 KB |
Output is correct |
| 7 |
Correct |
133 ms |
19604 KB |
Output is correct |
| 8 |
Correct |
1818 ms |
58800 KB |
Output is correct |
| 9 |
Correct |
1690 ms |
58784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1732 ms |
58948 KB |
Output is correct |
| 2 |
Correct |
1158 ms |
68792 KB |
Output is correct |
| 3 |
Correct |
1145 ms |
68924 KB |
Output is correct |
| 4 |
Correct |
1135 ms |
68976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
15188 KB |
Output is correct |
| 2 |
Correct |
7 ms |
15188 KB |
Output is correct |
| 3 |
Correct |
8 ms |
15188 KB |
Output is correct |
| 4 |
Correct |
9 ms |
15188 KB |
Output is correct |
| 5 |
Correct |
13 ms |
15444 KB |
Output is correct |
| 6 |
Correct |
86 ms |
17544 KB |
Output is correct |
| 7 |
Correct |
1419 ms |
38732 KB |
Output is correct |
| 8 |
Correct |
1690 ms |
58868 KB |
Output is correct |
| 9 |
Correct |
237 ms |
38808 KB |
Output is correct |
| 10 |
Correct |
1146 ms |
44852 KB |
Output is correct |
| 11 |
Correct |
716 ms |
56920 KB |
Output is correct |
| 12 |
Correct |
717 ms |
56876 KB |
Output is correct |
| 13 |
Correct |
1187 ms |
68996 KB |
Output is correct |
