제출 #937463

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
937463		william950615	Cat Exercise (JOI23_ho_t4)	C++14	21 / 100	128 ms	51124 KiB

Main

#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>;

#ifdef LOCAL
int __lg( int x ) {
	return 31 - __builtin_clz( x );
}
#endif
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();
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26