#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define eb emplace_back
const int maxn=1e5+9;
vector<int>a[maxn];
int sub[maxn];
int dep[maxn];
int p[maxn];
void dfs(int u,int par){
sub[u]=1;
for (auto &v:a[u]){
if (v==par)continue;
dep[v]=dep[u]+1;
p[v]=u;
dfs(v,u);
sub[u]+=sub[v];
if (a[u][0]==par||sub[a[u][0]]<sub[v])swap(v,a[u][0]);
}
}
int pos[maxn],h[maxn],b[maxn];
int tme=0,gr=1;
void hld(int u,int par,int head){
h[u]=head;
pos[u]=++tme;
b[u]=gr;
if (a[u].empty())return;
if (a[u][0]!=par){
hld(a[u][0],u,head);
}
for (auto v:a[u]){
if (v==par||v==a[u][0])continue;
gr++;
hld(v,u,v);
}
}
int bit[maxn];
int n,m,q;
void add(int ps,int val){
if (ps==0)return;
for(;ps<=n;ps+=(ps-(ps&(ps-1))))bit[ps]+=val;
}
int get(int ps){
int sum=0;
for(;ps>=1;ps-=(ps-(ps&(ps-1))))sum+=bit[ps];
return sum;
}
int get(int l,int r){
return get(r)-get(l-1);
}
struct tim{
int l,r,w;
bool operator < (const tim &p1)const {
return l<p1.l;
}
};
multiset<tim>line[maxn];
multiset<tim>::iterator it;
void update(int u,int v,int w){
while (h[u]!=h[v]){
if (dep[h[u]]<dep[h[v]])swap(u,v);
//cout<<u<<" "<<v<<'\n';
tim tmp={pos[h[u]],pos[u],w};
int id=b[u];
while (!line[id].empty()){
it=line[id].begin();
auto temp=(*it);
if (temp.l>tmp.r)break;
add(temp.w,-(temp.r-temp.l+1));
if (temp.r<=tmp.r){
line[id].erase(it);
}
else {
line[id].erase(it);
temp.l=tmp.r+1;
line[id].insert(temp);
add(temp.w,temp.r-tmp.r);
}
}
add(tmp.w,tmp.r-tmp.l+1);
line[id].insert(tmp);
u=p[h[u]];
}
if (pos[u]>pos[v])swap(u,v);
tim tmp={pos[u],pos[v],w};
//cerr<<u<<" "<<v<<'\n';
//cerr<<pos[u]<<" "<<pos[v]<<'\n';
//if (w==5)cerr<<pos[u]<<" "<<pos[v]<<'\n';
int id=b[u];
while (!line[id].empty()){
it=line[id].upper_bound(tmp);
if (it==line[id].begin())break;
//cerr<<"haha"<<'\n';
it--;
auto temp=(*it);
if (temp.r<tmp.l)break;
add(temp.w,-(temp.r-temp.l+1));
line[id].erase(it);
if (temp.r>tmp.r){
tim t1={tmp.r+1,temp.r,temp.w};
add(temp.w,temp.r-tmp.r);
temp.r=tmp.r;
line[id].insert(t1);
}
if (temp.l<tmp.l){
temp.r=tmp.l-1;
add(temp.w,temp.r-temp.l+1);
line[id].insert(temp);
}
}
while (!line[id].empty()){
it=line[id].lower_bound(tmp);
if (it==line[id].end())break;
auto temp=(*it);
//cerr<<temp.l<<" "<<temp.r<<'\n';
if (temp.l>tmp.r)break;
add(temp.w,-(temp.r-temp.l+1));
line[id].erase(it);
if (temp.r<=tmp.r)continue;
temp.l=tmp.r+1;
add(temp.w,temp.r-temp.l+1);
line[id].insert(temp);
}
add(tmp.w,tmp.r-tmp.l+1);
line[id].insert(tmp);
}
int city[maxn];
vector<pii>query[maxn];
int ans[maxn];
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("temp.INP","r",stdin);
//freopen("temp.OUT","w",stdout);
cin>>n>>m>>q;
for1(i,1,n-1){
int u,v;
cin>>u>>v;
a[u].pb(v);
a[v].pb(u);
}
dfs(1,0);
hld(1,0,1);
for1(i,1,m)cin>>city[i];
for1(i,1,q){
int l,r;
cin>>l>>r;
if (l==r){
ans[i]=1;
//cerr<<"xxx";
}
else {
query[r].pb({l,i});
}
}
for1(i,2,m){
update(city[i],city[i-1],i-1);
for (auto v:query[i]){
ans[v.se]=get(v.fi,i);
}
}
//for1(i,1,n)cout<<pos[i]<<'\n';
//for (auto v:line[1])cout<<v.l<<" "<<v.r<<'\n';
/*for1(i,1,m){
cout<<i<<" "<<get(i,i)<<'\n';
}*/
//update(4,5,4);
//update(5,1,5);
//for1(i,1,n)cout<<i<<" "<<pos[i]<<'\n';
//for (auto v:line[2])cout<<v.l<<" "<<v.r<<'\n';
for1(i,1,q)cout<<ans[i]<<'\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
4 ms |
9684 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
4 ms |
9684 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9736 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
9728 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9736 KB |
Output is correct |
| 2 |
Correct |
95 ms |
16168 KB |
Output is correct |
| 3 |
Incorrect |
127 ms |
17188 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9656 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
4 ms |
9684 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
