#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cassert>
#include<set>
#include<utility>
using namespace std;
const int k = 300;
vector<vector<int>> graph;
vector<int> in, dep, pos;
vector<vector<int>> anc;
int tst = 0;
void dfs(int node, int parent){
in[++tst] = node;
pos[node] = tst;
anc[0][node] = parent;
dep[node] = dep[parent] + 1;
for(auto x: graph[node]){
if(x == parent) continue;
dfs(x, node);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
//assert(n <= 2000);
in.resize(n + 1);
dep.resize(n + 1);
pos.resize(n + 1);
anc.resize(18, vector<int>(n + 1));
graph.resize(n + 1);
int a, b;
for(int i = 1; i < n; i++){
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
dfs(1, 1);
vector<int> vec(m + 1);
for(int i = 1; i <= m; i++) cin >> vec[i], vec[i] = pos[vec[i]];
vector<int> ans(q);
for(int i = 1; i < 18; i++){
for(int j = 1; j <= n; j++){
anc[i][j] = anc[i - 1][anc[i - 1][j]];
}
}
auto lca = [&](int u, int v){
u = in[u], v = in[v];
if(dep[u] < dep[v]) swap(u, v);
for(int i = 17; i >= 0; i--){
if((1 << i) & (dep[u] - dep[v])) u = anc[i][u];
}
for(int i = 17; i >= 0; i--){
if(anc[i][u] != anc[i][v]) u = anc[i][u], v = anc[i][v];
}
if(u != v) u = anc[0][u], v = anc[0][v];
return pos[u];
};
auto dist = [&](int u, int v){
return dep[in[u]] + dep[in[v]] - 2 * dep[in[lca(u, v)]];
};
auto left = [&](int aa, int bb, int cc){
return (dist(aa, bb) + dist(aa, cc) - dist(bb, cc)) / 2;
};
vector<pair<pair<int, int>, int>> queries;
for(int i = 0; i < q; i++){
cin >> a >> b;
queries.push_back(make_pair(make_pair(a, b), i));
}
auto cmp = [&](pair<pair<int, int>, int> c, pair<pair<int, int>, int> d){
if((c.first.first - 1) / k == (d.first.first - 1) / k){
if((c.first.first - 1) / k % 2 == 0) return c.first.second < d.first.second;
else return c.first.second > d.first.second;
}
else return (c.first.first - 1) / k < (d.first.first - 1) / k;
};
sort(queries.begin(), queries.end(), cmp);
int now_lca = 1;
multiset<int> s;
int cnt = 0;
vector<vector<int>> st(18, vector<int>(m + 1));
for(int i = 1; i <= m; i++) st[0][i] = vec[i];
for(int i = 1; i < 18; i++){
for(int j = 1; j <= m; j++) st[i][j] = lca(st[i - 1][j], st[i - 1][min(m, j + (1 << (i - 1)))]);
}
vector<int> bases(n + 1);
int tmp = 0;
for(int i = 1; i <= n; i++){
if((1 << (tmp + 1)) <= i) tmp++;
bases[i] = tmp;
}
auto query = [&](int l, int r){
tmp = r - l + 1;
return lca(st[bases[tmp]][l], st[bases[tmp]][r - (1 << bases[tmp]) + 1]);
};
int lptr = 1, rptr = 0;
auto add = [&](int node){
if(s.empty()){
now_lca = node;
s.insert(node);
cnt = 1;
return;
}
auto iter = s.lower_bound(node);
if(iter != s.end() && (*iter) == node){
s.insert(node);
return;
}
if(iter == s.begin()){
cnt += left(node, (*iter), now_lca);
now_lca = lca(node, now_lca);
s.insert(node);
return;
}
if(iter == s.end()){
iter = prev(iter);
cnt += left(node, (*iter), now_lca);
now_lca = lca(node, now_lca);
s.insert(node);
return;
}
int bf = (*prev(iter)), gf = (*iter);
cnt += left(node, bf, gf);
s.insert(node);
now_lca = lca(node, now_lca);
};
auto sub = [&](int node){
auto iter = s.lower_bound(node);
s.erase(iter);
if(s.empty()) return;
iter = s.lower_bound(node);
if(iter != s.end() && (*iter) == node){
return;
}
if(iter == s.begin()){
cnt -= left(node, (*iter), now_lca);
now_lca = query(lptr, rptr);
return;
}
if(iter == s.end()){
iter = prev(iter);
cnt -= left(node, (*iter), now_lca);
now_lca = query(lptr, rptr);
return;
}
int bf = (*prev(iter)), gf = (*iter);
cnt -= left(node, bf, gf);
now_lca = query(lptr, rptr);
};
for(auto &x: queries){
a = x.first.first, b = x.first.second;
while(a < lptr) add(vec[--lptr]);
while(rptr < b) add(vec[++rptr]);
while(lptr < a) lptr++, sub(vec[lptr - 1]);
while(b < rptr) rptr--, sub(vec[rptr + 1]);
ans[x.second] = cnt;
//cout << now_lca;
}
for(int i = 0; i < q; i++) cout << ans[i] << "\n";
}
// g++ -std=c++17 pC.cpp -o run -fsanitize=undefined -fsanitize=address -Wall -Wextra -Wshadow -Wfatal-errors
/*
7 6 2
1 2
1 3
2 4
2 5
3 6
3 7
2 3 6 4 5 7
1 3
4 6
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
265 ms |
12588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
16 ms |
516 KB |
Output is correct |
| 4 |
Runtime error |
268 ms |
40656 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
