#define ll long long
#define pll pair<ll, ll>
#define INF numeric_limits<int>::max()/2
#include <bits/stdc++.h>
using namespace std;
void init(ll i, vector<ll>& depth, vector<vector<ll>>& adjlist, vector<bool>& visited, vector<ll>& subtree, vector<vector<ll>>& jump)
{
visited[i] = true;
for(ll j : adjlist[i])
{
if(visited[j])
{
jump[0][i] = j;
depth[i] = depth[j]+1;
}
}
for(ll j : adjlist[i])
{
if(!visited[j])
{
init(j, depth, adjlist, visited, subtree, jump);
subtree[i] += subtree[j];
}
}
}
ll lift(ll a, vector<vector<ll>>& jump, ll dist)
{
for(ll i = jump.size()-1; i >= 0 && a != -1; i--)
{
if(((1<<i)&dist) != 0)
{
a = jump[i][a];
}
}
return a;
}
ll lca(ll a, ll b, vector<vector<ll>>& jump, vector<ll>& depth)
{
if(depth[a] < depth[b])
swap(a, b);
a = lift(a, jump, depth[a]-depth[b]);
if(a == b)
{
return a;
}
for(ll j = jump.size()-1; j >= 0; j--)
{
if(jump[j][a] != jump[j][b])
{
a = jump[j][a];
b = jump[j][b];
}
}
return jump[0][a];
}
ll left(ll i)
{
return 2*i;
}
ll right(ll i)
{
return 2*i+1;
}
pll conjugate(pll a, pll b)
{
return {max(a.first, b.first), min(a.second, b.second)};
}
pll query3(ll i, vector<pll>& s, ll a, ll b, ll l, ll r)
{
if(l <= a && b <= r)
{
return s[i];
}
if(b < l || r < a)
{
return {-1, INF};
}
ll mid = (a+b)/2;
return conjugate(query3(left(i), s, a, mid, l, r), query3(right(i), s, mid+1, b, l, r));
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll n, m, q;
cin>>n>>m>>q;
vector<vector<ll>> adjlist(n, vector<ll> (0));
bool sub3 = true;
for(ll i = 0; i < n-1; i++)
{
ll a, b;
cin>>a>>b;
a--; b--;
if(a != i || b != i+1)
{
sub3 = false;
}
adjlist[a].push_back(b);
adjlist[b].push_back(a);
}
ll segnodes = 1;
ll logdepth = 0;
while(2*n > segnodes)
{
segnodes *= 2;
logdepth++;
}
vector<vector<ll>> jump(logdepth, vector<ll> (n, -1));
vector<ll> subtree(n, 1);
vector<bool> visited(n, false);
vector<ll> depth(n, 0);
init(0, depth, adjlist, visited, subtree, jump);
for(ll i = 1; i < logdepth; i++)
{
for(ll j = 0; j < n; j++)
{
if(jump[i-1][j] != -1)
{
jump[i][j] = jump[i-1][jump[i-1][j]];
}
}
}
vector<ll> c(m);
for(ll i = 0; i < m; i++)
{
cin>>c[i];
c[i]--;
}
vector<pll> s3(segnodes, {-1, INF}); //Max, min
if(sub3)
{
for(ll i = 0; i < n; i++)
{
s3[i+segnodes/2].first = depth[c[i]];
s3[i+segnodes/2].second = depth[c[i]];
}
for(ll i = segnodes/2-1; i > 0; i--)
{
s3[i].first = max(s3[left(i)].first, s3[right(i)].first);
s3[i].second = min(s3[left(i)].second, s3[right(i)].second);
}
}
assert(sub3);
for(ll x = 0; x < q; x++)
{
ll left, right;
cin>>left>>right;
left--; right--;
if(left == right)
{
cout<<1<<"\n";
continue;
}
if(sub3)
{
pll range = query3(1, s3, 1, segnodes/2, left+1, right+1);
cout<<range.first+1-range.second<<"\n";
continue;
}
ll l = lca(c[left], c[left+1], jump, depth);
for(ll i = left+2; i <= right; i++)
{
l = lca(l, c[i], jump, depth);
}
visited.assign(n, false);
visited[l] = true;
ll counter = 1;
for(ll i = left; i <= right; i++)
{
ll node = c[i];
while(!visited[node])
{
visited[node] = true;
counter++;
node = jump[0][node];
}
}
cout<<counter<<"\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
