Submission #927277

#	Time	Username	Problem	Language	Result	Execution time	Memory
927277		belgianbot	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	458 ms	67412 KiB

Main

#include <bits/stdc++.h>

using namespace std;

vector <vector<int> > connections, up, child;
vector <int> p, parent, depth;
int N, LOG;
	

void dfs(int a, int pa) {
	for (int b : connections[a]) {
		if(b == pa) continue;
		depth[b] = depth[a] + 1;
		up[b][0] = a;
		for (int i(1); i < LOG; i++) 
			up[b][i] = up[ up[b][i - 1] ][i - 1];
		dfs(b, a);
	}
}
int lca(int a, int b) {
	if (depth[a] < depth[b])
		swap(a, b);
		
	int k = depth[a] - depth[b];
	for (int i(LOG); i >= 0; i--) {
		if (k & (1 << i))
			a = up[a][i];
	}
	
	if (a == b)
		return a;
	
	for (int i(LOG); i >= 0; i--) {
		if (up[a][i] != up[b][i]) {
			a = up[a][i];
			b = up[b][i];
		}
	}
	
	return up[a][0];
}
int Find(int x) {
	if (x == parent[x]) return x;
	return Find(parent[x]);
}

void Merge(int a, int b) {
	int pb = Find(b);
	
	child[a].push_back(pb);
	parent[pb] = a;
}

long long score(int x) {
	long long ans(0);
	for (int i : child[x]) {
		int root = lca(x, i);
		ans = max(ans, score(i) + (long long)(depth[x] + depth[i] - 2 * depth[root]));
	}
	return ans;
}
int main() {
	cin >> N;
	LOG = ceil(log2(N));
	connections.resize(N); p.resize(N), parent.resize(N); depth.resize(N); up.resize(N, vector<int> (LOG + 1, N - 1)); child.resize(N);
	for (int i(0); i < N; i++) {
		cin >> p[i];
		p[i]--;
		parent[i] = i;
	}
	

	for (int i(0); i < N - 1; i++) {
		int a, b; cin >> a >> b;
		a--; b--;
		connections[p[a]].push_back(p[b]);
		connections[p[b]].push_back(p[a]);
	}
	
	depth[N - 1] = 0;
	dfs(N - 1, -1);
	for (int i(1); i < N; i++) {
		for (int j : connections[i]) {
			if (j < i) Merge(i, j);
		}
	}
	
	cout << score(N - 1) << '\n';
		
	return 0;
}
	
	

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