#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = (1 << 17) ;
bool flag1, flag2, us[N + 1] ;
int n, m, q, c[N + 1], l[N + 1], r[N + 1], p[N + 1], dist[N + 1], ind[N + 1], pw[2 * N + 1] ;
vector<int> v[N + 1] ;
vector<pair<int, int>> tree ;
int mx[N + 1][20], mn1[N + 1][20] ;
pair<int, int> mn[2 * N + 1][20] ;
//ниже всё для hld
vector<int> hld ;
int kol[N + 1], index[N + 1], tp[N + 1], bst[N + 1], sum[2 * N + 1], psh[2 * N + 1] ;
void first_dfs(int city, int last)
{
int now = 0 ;
kol[city]++ ;
for(int i : v[city])
{
if(i == last)
continue ;
first_dfs(i, city) ;
kol[city] += kol[i] ;
if(now < kol[i])
{
now = max(now, kol[i]) ;
bst[city] = i ;
}
}
}
void second_dfs(int city, int last, int gay)
{
tp[city] = gay ;
index[city] = hld.size() ;
hld.push_back(city) ;
if(bst[city])
second_dfs(bst[city], city, gay) ;
for(int i : v[city])
{
if(i == last || i == bst[city])
continue ;
second_dfs(i, city, hld.size()) ;
}
}
void push(int l, int r, int v)
{
if(psh[v] == -1)
return ;
int num = psh[v] ;
psh[v] = -1 ;
sum[v] = num * (r - l + 1) ;
if(l == r)
return ;
psh[v * 2] = num ;
psh[v * 2 + 1] = num ;
}
void build()
{
for(int i = 1 ; i <= 2 * N ; i++)
psh[i] = -1 ;
}
void update(int l, int r, int l1, int r1, int num, int v)
{
push(l, r, v) ;
if(l > r1 || r < l1)
return ;
if(l1 <= l && r <= r1)
{
psh[v] = num ;
push(l, r, v) ;
return ;
}
int mid = (l + r) >> 1 ;
update(l, mid, l1, r1, num, v * 2) ;
update(mid + 1, r, l1, r1, num, v * 2 + 1) ;
sum[v] = sum[v * 2] + sum[v * 2 + 1] ;
}
//конец hld
void dfs(int city, int last)
{
ind[city] = tree.size() ;
tree.push_back({dist[city], city}) ;
p[city] = last ;
for(int i : v[city])
{
if(i == last)
continue ;
dist[i] = dist[city] + 1 ;
dfs(i, city) ;
tree.push_back({dist[city], city}) ;
}
}
void build_lca()
{
for(int i = 2 ; i <= tree.size() ; i++)
pw[i] = pw[i / 2] + 1 ;
for(int i = 0 ; i < tree.size() ; i++)
mn[i][0] = tree[i] ;
for(int i = 1 ; i < 20 ; i++)
for(int j = 0 ; j <= (int)tree.size() - (1 << i) ; j++)
mn[j][i] = min(mn[j][i - 1], mn[j + (1 << (i - 1))][i - 1]) ;
}
int get_lca(int a, int b)
{
a = ind[a] ;
b = ind[b] ;
if(a > b)
swap(a, b) ;
int num = pw[b - a + 1] ;
return min(mn[a][num], mn[b - (1 << num) + 1][num]).se ;
}
void build_mx_mn()
{
for(int i = 2 ; i <= m ; i++)
pw[i] = pw[i / 2] + 1 ;
for(int i = 1 ; i <= m ; i++)
mn1[i][0] = c[i], mx[i][0] = c[i] ;
for(int i = 1 ; i < 20 ; i++)
for(int j = 1 ; j <= m - (1 << i) + 1 ; j++)
mn1[j][i] = min(mn1[j][i - 1], mn1[j + (1 << (i - 1))][i - 1]),
mx[j][i] = max(mx[j][i - 1], mx[j + (1 << (i - 1))][i - 1]) ;
}
pair<int, int> get_mn_mx(int a, int b)
{
int num = pw[b - a + 1] ;
return {min(mn1[a][num], mn1[b - (1 << num) + 1][num]), max(mx[a][num], mx[b - (1 << num) + 1][num])} ;
}
signed main()
{
ios_base::sync_with_stdio( 0 ) ;
cin.tie( 0 ) ;
cout.tie( 0 ) ;
cin >> n >> m >> q ;
for(int i = 1 ; i < n ; i++)
{
int a, b ;
cin >> a >> b ;
if(a != i || b != i + 1)flag1 = 1 ;
v[a].push_back(b) ;
v[b].push_back(a) ;
}
for(int i = 1 ; i <= m ; i++)
cin >> c[i] ;
for(int i = 1 ; i <= q ; i++)
cin >> l[i] >> r[i] ;
for(int i = 1 ; i < q ; i++)
if(r[i] + 1 != l[i + 1])
flag2 = 1 ;
if(!flag1)
{
build_mx_mn() ;
for(int i = 1 ; i <= q ; i++)
{
pair<int, int> p = get_mn_mx(l[i], r[i]) ;
cout << p.se - p.fi + 1 << '\n' ;
}
return 0 ;
}
if(n <= 2000 && m <= 2000 && q <= 2000)
{
us[0] = 1 ;
dfs(1, 0) ;
build_lca() ;
for(int i = 1 ; i <= q ; i++)
{
int ans = 0, lc = c[l[i]] ;
for(int j = l[i] + 1 ; j <= r[i] ; j++)
lc = get_lca(lc, c[j]) ;
for(int j = l[i] ; j <= r[i] ; j++)
{
int now = c[j] ;
while(!us[now])
{
ans++ ;
us[now] = 1 ;
if(now == lc)
break ;
now = p[now] ;
}
}
for(int i = 1 ; i <= n ; i++)
us[i] = 0 ;
cout << ans << '\n' ;
}
return 0 ;
}
if(!flag2)
{
dfs(1, 0) ;
build_lca() ;
first_dfs(1, 0) ;
second_dfs(1, 0, 0) ;
build() ;
// cout << "hld\n" ;
// for(int i : hld)
// cout << i << ' ' << tp[i] << '\n' ;
// cout << "__________________\n" ;
for(int i = 1 ; i <= q ; i++)
{
int lc = c[l[i]] ;
for(int j = l[i] + 1 ; j <= r[i] ; j++)
lc = get_lca(lc, c[j]) ;
for(int j = l[i] ; j <= r[i] ; j++)
{
int now = c[j] ;
while(now != lc)
if(index[lc] < tp[now])
{
update(0, N - 1, tp[now], index[now], 1, 1) ;
now = p[hld[tp[now]]] ;
}
else
{
update(0, N - 1, index[lc], index[now], 1, 1) ;
now = lc ;
}
}
cout << sum[1] << '\n' ;
psh[1] = 0 ;
}
return 0 ;
}
return 0 ;
}
Compilation message
tourism.cpp:15:28: error: 'int index [131073]' redeclared as different kind of entity
15 | int kol[N + 1], index[N + 1], tp[N + 1], bst[N + 1], sum[2 * N + 1], psh[2 * N + 1] ;
| ^
In file included from /usr/include/string.h:432,
from /usr/include/c++/10/cstring:42,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:48,
from tourism.cpp:1:
/usr/include/strings.h:61:1: note: previous declaration 'const char* index(const char*, int)'
61 | index (const char *__s, int __c) __THROW
| ^~~~~
tourism.cpp: In function 'void second_dfs(int, int, int)':
tourism.cpp:36:10: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
36 | index[city] = hld.size() ;
| ^
tourism.cpp: In function 'void build_lca()':
tourism.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i = 2 ; i <= tree.size() ; i++)
| ~~^~~~~~~~~~~~~~
tourism.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i = 0 ; i < tree.size() ; i++)
| ~~^~~~~~~~~~~~~
tourism.cpp: In function 'int main()':
tourism.cpp:209:29: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
209 | if(index[lc] < tp[now])
| ^
tourism.cpp:211:56: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
211 | update(0, N - 1, tp[now], index[now], 1, 1) ;
| ^
tourism.cpp:216:47: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
216 | update(0, N - 1, index[lc], index[now], 1, 1) ;
| ^
tourism.cpp:216:58: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
216 | update(0, N - 1, index[lc], index[now], 1, 1) ;
| ^
