#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<vector<pair<pair<int, int>, int>>> queries(m / k + 1);
for(int i = 0; i < q; i++){
cin >> a >> b;
queries[(a - 1) / k].push_back(make_pair(make_pair(a, b), i));
}
auto cmp = [&](pair<pair<int, int>, int> c, pair<pair<int, int>, int> d){
return c.first.second < d.first.second;
};
for(int i = 0; i <= m / k; i++) sort(queries[i].begin(), queries[i].end(), cmp);
int lb = 0, now_lca = -1;
for(auto &x: queries){
lb += k;
multiset<int> s;
int cnt = 0, rb = lb, last_cnt = 0;
auto add = [&](int node){
if(s.empty()){
now_lca = node;
s.insert(node);
cnt = 1;
return;
}
auto iter = s.upper_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);
//cout << node << " " << left(node, (*iter), now_lca) << "\n";
//cout << node << " " << (*iter) << " " << now_lca << "\n";
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);
};
for(auto &y: x){
a = y.first.first, b = y.first.second;
while(b > rb){
rb++;
//add(vec[rb]);
}
last_cnt = cnt;
for(int i = a; i <= min(b, lb); i++){
cnt = cnt * cnt % n;
//add(vec[i]);
}
ans[y.second] = cnt;
cnt = last_cnt;
for(int i = a; i <= min(b, lb); i++){
//s.erase(s.find(vec[i]));
cnt = cnt * cnt % n;
}
//cout << cnt << "\n";
}
}
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
/*
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
*/
Compilation message
tourism.cpp: In function 'int main()':
tourism.cpp:82:14: warning: variable 'add' set but not used [-Wunused-but-set-variable]
82 | auto add = [&](int node){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
