#include<iostream>
#include<vector>
#include<set>
#include<utility>
#include<cassert>
#include<algorithm>
using namespace std;
int n, m, q;
vector<vector<int>> graph, anc;
vector<int> vec, in, out, ord, head, sz, bit, dep;
int cnt = 0;
void dfs(int node, int parent){
ord[++cnt] = node;
in[node] = cnt;
sz[node] = 1;
anc[0][node] = parent;
head[node] = node;
dep[node] = dep[parent] + 1;
int maxi = 0, pos = -1;
for(auto &x: graph[node]){
if(x == parent) continue;
dfs(x, node);
sz[node] += sz[x];
if(maxi < sz[x]){
maxi = sz[x];
pos = x;
}
}
if(pos > 0) head[pos] = node;
out[node] = cnt;
}
void dfs_head(int node, int parent){
if(head[node] != node) head[node] = head[parent];
for(auto &x: graph[node]){
if(x != parent) dfs_head(x, node);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> q;
graph.resize(n + 1);
vec.resize(m + 1);
in.resize(n + 1);
out.resize(n + 1);
ord.resize(n + 1);
head.resize(n + 1);
sz.resize(n + 1);
dep.resize(n + 1);
for(int i = 1; i < n; i++){
int a, b;
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
anc.resize(18, vector<int>(n + 1));
dfs(1, 1);
//dfs_head(1, 1);
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 a, int b){
if(dep[a] < dep[b]) swap(a, b);
for(int i = 0; i < 18; i++){
if((dep[a] - dep[b]) & (1 << i)) a = anc[i][a];
}
for(int i = 17; i >= 0; i--){
if(anc[i][a] != anc[i][b]){
a = anc[i][a];
b = anc[i][b];
}
}
if(a != b) return anc[0][a];
else return a;
};
bit.resize(m + 1);
for(int i = 1; i <= m; i++) cin >> vec[i];
auto modify = [&](int pos, int val){
while(pos <= m){
bit[pos] += val;
pos += (pos & -pos);
}
};
auto query = [&](int pos){
int ans = 0;
while(pos > 0){
ans += bit[pos];
pos -= (pos & -pos);
}
return ans;
};
vector<vector<pair<int, int>>> sweep(m + 1);
vector<int> ans(q);
for(int i = 0; i < q; i++){
int l, r;
cin >> l >> r;
sweep[r].emplace_back(l, i);
}
vector<vector<int>> st(18, vector<int>(m));
for(int i = 1; i < m; i++) st[0][i] = lca(vec[i], vec[i + 1]);
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 - 1, j + (1 << (i - 1)))]);
}
vector<int> bases(m);
for(int i = 2; i < m; i++){
bases[i] = bases[i - 1];
if((1 << (bases[i] + 1)) == i) bases[i]++;
}
auto qlca = [&](int l, int r){
r--;
if(l > r) return vec[l];
int len = r - l + 1;
return lca(st[bases[len]][l], st[bases[len]][r - (1 << bases[len]) + 1]);
};
set<pair<pair<int, int>, int>> s;
auto assign = [&](int l, int r, int col){
//cout << l << " " << r << " " << col << "\n";
while(!s.empty()){
auto iter = s.lower_bound(make_pair(make_pair(l, 0), 0));
if(iter == s.end()) break;
auto [rng, scol] = (*iter);
if(rng.first > r) break;
s.erase(iter);
modify(scol, -(rng.second - rng.first + 1));
if(rng.second > r){
modify(scol, rng.second - r);
s.insert(make_pair(make_pair(r + 1, rng.second), scol));
}
}
auto iter2 = s.lower_bound(make_pair(make_pair(l, 0), 0));
if(iter2 != s.begin()){
iter2 = prev(iter2);
if((*iter2).first.second >= l){
auto [rng2, col2] = (*iter2);
s.erase(iter2);
modify(col2, -(rng2.second - l + 1));
s.insert(make_pair(make_pair(rng2.first, l - 1), col2));
if(r < rng2.second){
modify(col2, rng2.second - r);
s.insert(make_pair(make_pair(r + 1, rng2.second), col2));
}
}
}
s.insert(make_pair(make_pair(l, r), col));
modify(col, r - l + 1);
};
for(int i = 1; i <= m; i++){
int cur = vec[i];
while(1){
assign(in[head[cur]], in[cur], i);
if(head[cur] == 1) break;
cur = anc[0][head[cur]];
}
for(auto &[l, id]: sweep[i]){
ans[id] += query(i) - query(l - 1);
ans[id] -= dep[qlca(l, i)];
}
}
for(int i = 0; i < q; i++){
cout << ans[i] + 1 << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
3 ms |
716 KB |
Output is correct |
| 4 |
Execution timed out |
5099 ms |
26328 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
340 ms |
15012 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
3 ms |
736 KB |
Output is correct |
| 4 |
Correct |
633 ms |
23536 KB |
Output is correct |
| 5 |
Correct |
625 ms |
24300 KB |
Output is correct |
| 6 |
Correct |
681 ms |
29976 KB |
Output is correct |
| 7 |
Correct |
722 ms |
32904 KB |
Output is correct |
| 8 |
Correct |
731 ms |
32796 KB |
Output is correct |
| 9 |
Correct |
728 ms |
32892 KB |
Output is correct |
| 10 |
Correct |
712 ms |
32928 KB |
Output is correct |
| 11 |
Correct |
722 ms |
32704 KB |
Output is correct |
| 12 |
Correct |
703 ms |
32728 KB |
Output is correct |
| 13 |
Correct |
683 ms |
32960 KB |
Output is correct |
| 14 |
Correct |
143 ms |
13504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
