#include<bits/stdc++.h>
using namespace std ;
#define maxn 200009
#define ll long long
#define fi first
#define se second
#define pb push_back
#define left id<<1
#define right id<<1|1
#define re exit(0);
const int mod = 1e9+7 ;
const int INF = 1e9 ;
const int LOG = 18 ;
typedef vector<int> vi ;
typedef vector<ll> vl ;
typedef pair<int,int> pii ;
typedef vector<pii> vii ;
typedef pair<ll,ll> pll ;
void add ( int &a , int b )
{
a += b ;
if ( a < 0 ) a += mod ;
if ( a >= mod ) a -= mod ;
}
template < typename T > void chkmin (T &a , T b) { if (a>b) a=b ;}
template < typename T > void chkmax (T &a , T b) { if (a<b) a=b ;}
void rf ()
{
freopen ("bai1.inp","r",stdin) ;
// freopen ("bai1.out","w",stdout) ;
}
int n , m , nq ;
vi adjList [maxn] ;
int seeing [maxn] ;
pii query [maxn] ;
int par [maxn][20] , dep [maxn] , tin [maxn] , timeDfs ;
void dfs ( int u = 1 )
{
tin [u] = ++ timeDfs ;
for ( auto v : adjList [u] )
{
if ( v == par [u][0] ) continue ;
par [v][0] = u , dep [v] = dep [u] + 1 ;
for ( int i = 1 ; i <= LOG ; i ++ ) par [v][i] = par[par[v][i-1]][i-1] ;
dfs (v) ;
}
}
int lca ( int u , int v )
{
if ( dep [u] < dep [v] ) swap (u,v) ;
int h = dep [u] - dep [v] ;
for ( int i = LOG ; i >= 0 ; i -- ) if ( h >> i & 1 ) u = par [u][i] ;
if ( u == v ) return u ;
for ( int i = LOG ; i >= 0 ; i -- ) if ( par [u][i] != par [v][i] ) u = par [u][i] , v = par [v][i] ;
return par [u][0] ;
}
int dis ( int u , int v )
{
return dep [u] + dep [v] - 2*dep[lca(u,v)] ;
}
bool cmp ( int u , int v )
{
return tin [u] < tin [v] ;
}
void sub1 ()
{
for ( int run = 1 ; run <= nq ; run ++ )
{
int l = query [run].fi , r = query [run].se ;
vi v ;
for ( int i = l ; i <= r ; i ++ ) v . pb (seeing[i]) ;
sort (v.begin(),v.end(),cmp) ;
int last = 0 ;
int res = 0 ;
for ( auto x : v )
{
if ( last ) res += dis (last,x) ;
last = x ;
}
res += dis (last,v[0]) ;
cout << res / 2 + 1 << "\n" ;
}
}
bool is_line = true ;
int L [maxn][20][2] ;
int get_max ( int l , int r )
{
int x = __lg(r-l+1) ;
return max (L[l][x][1],L[r-(1<<x)+1][x][1]) ;
}
int get_min ( int l , int r )
{
int x = __lg(r-l+1) ;
return min (L[l][x][0],L[r-(1<<x)+1][x][0]) ;
}
void sub2 ()
{
for ( int i = 1 ; i <= m ; i ++ ) L [i][0][0] = L [i][0][1] = seeing [i] ;
for ( int j = 1 ; j <= __lg (m) ; j ++ )
{
for ( int i = 1 ; i <= m-(1<<j)+1 ; i ++ )
{
L [i][j][0] = min ( L[i][j-1][0],L[i+(1<<(j-1))][j-1][0]) ;
L [i][j][1] = max ( L[i][j-1][1],L[i+(1<<(j-1))][j-1][1]) ;
}
}
for ( int run = 1 ; run <= nq ; run ++ )
{
int l = query [run].fi , r = query [run].se ;
cout << get_max (l,r) - get_min (l,r) + 1 << "\n" ;
}
}
int main ()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ; cout.tie(0) ;
// rf () ;
cin >> n >> m >> nq ;
for ( int i = 1 ; i < n ; i ++ )
{
int u , v ; cin >> u >> v ;
if ( u != i || v != i + 1 ) is_line = false ;
adjList [u] . pb (v) ;
adjList [v] . pb (u) ;
}
for ( int i = 1 ; i <= m ; i ++ ) cin >> seeing [i] ;
for ( int i = 1 ; i <= nq ; i ++ ) cin >> query [i].fi >> query [i].se ;
dfs () ;
if ( is_line () ) sub2 () ;
else sub1 () ;
}
Compilation message
tourism.cpp: In function 'int main()':
tourism.cpp:148:16: error: 'is_line' cannot be used as a function
148 | if ( is_line () ) sub2 () ;
| ^
tourism.cpp: In function 'void rf()':
tourism.cpp:34:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | freopen ("bai1.inp","r",stdin) ;
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
