#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
vector <int> e[N];
vector <pair<int,int>> q2[N];
map <int,pair<int,int>> f;
int sub[N];
int top[N];
int st[N],cnt = 0;
int c[N];
int d[N];
int pr[N];
int ans[N];
int st2[N];
int n,m,q;
void dfs(int node, int p){
sub[node] = 1;
pr[node] = p;
if(p == -1){
d[node] = 0;
}else{
d[node] = d[p] + 1;
}
for(auto i:e[node]){
if(i == p)continue;
dfs(i, node);
sub[node]+=sub[i];
}
}
void dfs2(int node, int p){
int mxid = -1;
for(auto i:e[node]){
if(i == p)continue;
if(mxid == -1 || sub[mxid] < sub[i]){
mxid = i;
}
}
st[node] = cnt++;
st2[cnt - 1] = node;
if(mxid != -1){
top[mxid] = top[node];
dfs2(mxid, node);
}
for(auto i:e[node]){
if(i == p || i == mxid)continue;
top[i] = i;
dfs2(i, node);
}
}
int v[N];
void add(int u,int w,int id){
u = st[u];
w = st[w];
if(u > w)swap(u,w);
//cout<<u<<' '<<w<<' '<<id<<"updates\n";
///segment override
while(1){
auto x = f.lower_bound(u);
if(x == f.end() || x->first > w){
break;
}
int l = min(x->first,u),r = max(x->second.first,w),id2 = x->second.second;
f.erase(x);
if(l < u){
f[l] = {u - 1,id2};
}
if(w < r){
f[w + 1] = {r,id2};
}
}
auto x = f.lower_bound(u);
if(x != f.begin() && prev(x)->second.first >= u){
int l = min(x->first,u),r = max(x->second.first,w),id2 = x->second.second;
f.erase(x);
if(l < u){
f[l] = {u - 1,id2};
}
if(w < r){
f[w + 1] = {r,id2};
}
}
f[u] = {w,id};
}
int get(int pos){
int r = 0;
for(auto i:f){
if(i.second.second >= pos){
r+=i.second.first - i.first + 1;
}
//cout<<i.first<<' '<<i.second.first<<' '<<i.second.second<<'\n';
}
//cout<<'\n';
return r;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m>>q;
for(int i = 0;i < n - 1;i++){
int a,b;
cin>>a>>b;
a--;b--;
e[a].push_back(b);
e[b].push_back(a);
v[i] = -1;
}
v[n - 1] = -1;
dfs(0, -1);
top[0] = 0;
dfs2(0, -1);
for(int i = 0;i < m;i++){
cin>>c[i];
c[i]--;
}
for(int i = 0;i < q;i++){
int l,r;
cin>>l>>r;
if(l == r){
ans[i] = 1;
continue;
}
q2[r - 1].push_back({l - 1,i});
}
for(int i = 1;i < m;i++){
///add
int u = c[i],w = c[i - 1];
while(top[u] != top[w]){
if(d[top[u]] > d[top[w]])swap(u,w);
//cout<<w<<' '<<top[w]<<' '<<i - 1<<'\n';
add(w,top[w],i - 1);
w = pr[top[w]];
}
//cout<<u<<' '<<w<<' '<<i - 1<<'\n';
add(u,w,i - 1);
///queries
for(auto j:q2[i]){
ans[j.second] = get(j.first);
}
}
for(int i = 0;i < q;i++){
cout<<ans[i]<<'\n';
}
return 0;
}
/**
7 2 1
1 2
1 3
2 4
2 5
3 6
3 7
4 5
1 2
**/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6232 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4956 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6232 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4956 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4956 KB |
Output is correct |
| 2 |
Incorrect |
782 ms |
11512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4952 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 4 |
Execution timed out |
5045 ms |
15248 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6232 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4956 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
