#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mkp make_pair
#define MEM(x) memset(x,0,sizeof(x))
#define ALL(x) begin(x), end(x)
#define PH push
#define PB push_back
#define REP(i,N) for( int i = 0; i <(N); ++i )
#define FOR(i,a,b) for( int i = (a); i <= (b); ++i )
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
template<typename T>
using V = vector<T>;
int __lg( int x ) {
return 31 - __builtin_clz( x );
}
struct DSU {
const int N;
V<int> fth;
int find( int a ) { return a == fth[a] ? a : fth[a] = find(fth[a]);};
int merge( int a, int b ) { // make a be father
const int fa = find( a ), fb = find( b );
if( fa == fb ) return 0;
fth[ fb ] = fa;
return 1;
}
DSU( int N ) : N(N) {
fth.assign( N+1, 0 );
iota( ALL(fth), 0 );
}
};
struct LCA {
const int N;
int lgN, tm;
V<int> dis;
V<int> tin, tout;
V<V<int>> fth;
V<V<int>> G;
void dfs( int cur, int par ) {
tin[cur]=++tm;
for( int i = 1; i < lgN; ++i )
fth[ i ][ cur ] = fth[ i-1 ][ fth[i-1][cur] ];
for( auto &i : G[cur] ) {
if( i == par ) continue;
fth[ 0 ][ i ] = cur;
dis[ i ] = dis[ cur ] + 1;
dfs( i, cur );
}
tout[cur]=++tm;
}
bool isfather( int a, int b ) {
return tin[a] <= tin[b] && tout[b] <= tout[a];
}
int lca( int a, int b ) {
if( isfather(a,b) ) return a;
if( isfather(b,a) ) return b;
for( int i = lgN-1; i >= 0; --i ) {
if( !isfather( fth[ i ][ a ], b ) )
a = fth[ i ][ a];
}
return fth[ 0 ][ a ];
}
int Dis( int a, int b ) {
return dis[a]+dis[b]-2*dis[lca(a,b)];
}
LCA( V<V<int>>&_G, int N ) : N(N) {
tm = 0;
lgN = __lg( N ) + 1;
tin.assign( N+1, 0 );
tout.assign( N+1, 0 );
fth.assign( lgN, V<int>(N+1,0));
dis.assign( N+1, 0 );
G=_G;
dfs( 1, 0 );
V<V<int>>().swap( G );
}
};
void solve() {
int N; cin >> N;
V<int> NodeOf(N+1,0);
FOR(i,1,N) {
int p; cin >> p;
NodeOf[ p ] = i;
}
V<V<int>> G(N+1);
FOR(i,2,N) {
int a, b; cin >> a >> b;
G[a].PB( b );
G[b].PB( a );
}
LCA lca(G, N);
DSU dsu(N+1);
V<int> vis(N+1,0);
V<int> dp(N+1,0);
FOR(_,1,N) {
auto nd = NodeOf[_];
for( auto&j : G[nd] ) {
if( !vis[j] ) continue;
auto to = dsu.find( j );
dp[ nd ] = max( dp[ nd ], lca.Dis(nd,to) + dp[ to ] );
dsu.merge( nd, j );
}
vis[ nd ] = true;
}
cout << *max_element( ALL(dp) ) << '\n';
}
int main () {
int T=1;
#ifdef LOCAL
freopen( "input.txt", "r", stdin );
freopen( "output.txt", "w", stdout );
cin >> T;
#else
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
while(T--) solve();
}
Compilation message
Main.cpp: In constructor 'LCA::LCA(V<std::vector<int> >&, int)':
Main.cpp:89:17: error: call of overloaded '__lg(int&)' is ambiguous
89 | lgN = __lg( N ) + 1;
| ^
Main.cpp:21:5: note: candidate: 'int __lg(int)'
21 | int __lg( int x ) {
| ^~~~
In file included from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from Main.cpp:3:
/usr/include/c++/10/bits/stl_algobase.h:1366:3: note: candidate: 'constexpr int std::__lg(int)'
1366 | __lg(int __n)
| ^~~~
/usr/include/c++/10/bits/stl_algobase.h:1370:3: note: candidate: 'constexpr unsigned int std::__lg(unsigned int)'
1370 | __lg(unsigned __n)
| ^~~~
/usr/include/c++/10/bits/stl_algobase.h:1374:3: note: candidate: 'constexpr long int std::__lg(long int)'
1374 | __lg(long __n)
| ^~~~
/usr/include/c++/10/bits/stl_algobase.h:1378:3: note: candidate: 'constexpr long unsigned int std::__lg(long unsigned int)'
1378 | __lg(unsigned long __n)
| ^~~~
/usr/include/c++/10/bits/stl_algobase.h:1382:3: note: candidate: 'constexpr long long int std::__lg(long long int)'
1382 | __lg(long long __n)
| ^~~~
/usr/include/c++/10/bits/stl_algobase.h:1386:3: note: candidate: 'constexpr long long unsigned int std::__lg(long long unsigned int)'
1386 | __lg(unsigned long long __n)
| ^~~~
