Submission #857733

#	Time	Username	Problem	Language	Result	Execution time	Memory
857733		Hakiers	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	200 ms	45696 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5+7;
const int logx = 18;
vector<int> G[MAXN];
int jmp[MAXN][logx+1];
int t[MAXN];
int depth[MAXN];
int rep[MAXN];
int val[MAXN];
pair<ll, int> res[MAXN];
int n;

void connect(int a, int b){
	//cout << "connect: " << a << " " << b << "\n";
	G[a].push_back(b);
	G[b].push_back(a);
}

void dfs(int v, int p){
	depth[v] = depth[p] + 1;
	jmp[v][0] = p;
	
	for(int k = 1; k <=logx; k++)
		jmp[v][k] = jmp[jmp[v][k-1]][k-1];
		
	for(auto u : G[v])
		if(u != p) dfs(u, v);

}

int lca(int a, int b){
	if(depth[a] > depth[b]) swap(a, b);
	
	for(int k = logx; k >= 0; k--)
		if(depth[jmp[b][k]] >= depth[a])
			b = jmp[b][k];
			
	if(a == b)
		return a;
	
	for(int k = logx; k >= 0; k--){
		if(jmp[a][k] != jmp[b][k]){
			a = jmp[a][k];
			b = jmp[b][k];
		}
	}
	
	return jmp[a][0];
}

ll get_dist(int a, int b){
	return depth[a] + depth[b] - 2*depth[lca(a, b)];
}

int Find(int a){
	if(rep[a] == a)
		return a;
	return rep[a] = Find(rep[a]);
}

void Union(int a, int b){
	//cout << "a: " << a << " b: " << b << "\n";
	int tmpa = a;
	a = Find(a);
	b = Find(b);
	if(a == b) return;
	
	ll dist = get_dist(tmpa, res[b].second);
	pair<ll, int> sum = {res[b].first + dist, tmpa};
	
	
	if(val[a] < val[b]) swap(a, b);
	rep[b] = a;
	val[a] += val[b];
	res[a] = max({res[b], res[a], sum});
}


void merge(int v){

	for(auto u : G[v])
		 if(u < v) Union(v, u);
		 
	//cout << "res: " << v << " " << res[Find(v)].first << "\n";
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	
	for(int i = 1; i <= n; i++)
		cin >> t[i];
	
	for(int i = 1; i < n; i++){
		int a, b;
		cin >> a >> b;
		connect(t[a], t[b]);
	}
	
	dfs(n, n);
	
	for(int i = 1; i <= n; i++){
		rep[i] = i;
		val[i] = 1;
		res[i].second = i;
	}
	
	for(int i = 1; i <= n; i++) merge(i);
	
	cout << res[Find(n)].first << "\n";

}

/*
10
9 2 4 10 6 7 3 5 8 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10




*/

• 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