Submission #906506

#	Time	Username	Problem	Language	Result	Execution time	Memory
906506		Nonoze	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	628 ms	88792 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n;
vector<int> parent;
vector<bool> already;
vector<vector<int>> adj;
vector<int> vaut;
vector<vector<int>> adjbase;
vector<int> depth;
vector<vector<int>> up;


//LCA

int get_lca(int a, int b) {
	if (depth[a] < depth[b]) swap(a, b);
	int k=depth[a]-depth[b];
	for (int j=19; j>=0; j--) {
		if (k & (1<<j)) {
			a=up[a][j];
		}
	}
	if (a==b) return a;
	for (int j=19; j>=0; j--) {
		if (up[a][j]!=up[b][j]) {
			a=up[a][j];
			b=up[b][j];
		}
	}
	return up[a][0];
}

//UNION FIND

int getparent(int x) {
	if (x==parent[x]) return x;
	return parent[x]=getparent(parent[x]);
}

bool same(int a, int b) {
	return (getparent(a)==getparent(b));
}

void unite(int a, int b) {
	if (!already[a]) return;
	a=getparent(a);
	b=getparent(b);
	parent[a]=b;
	adj[b].push_back(a);
}


//INIT
void initdfs(int s, int last=-1) {
	for (auto u: adjbase[s]) {
		if (u==last) continue;
		depth[u] = depth[s]+1;
		up[u][0]=s;
		for (int i=1; i<20; i++) {
			up[u][i]=up[ up[u][i-1] ][i-1];
		}
		initdfs(u, s);
	}
}

//ANS CALCULATION

int calcans(int s) {
	int ans=0;
	for (auto u: adj[s]) {
		int add=depth[u]+depth[s]-2LL*depth[get_lca(u, s)];
		ans=max(ans, calcans(u)+add);
	}
	return ans;
}

void solve() {
	cin >> n;
	adj.resize(n+1);
	already.resize(n+1, false);
	adjbase.resize(n+1);
	vaut.resize(n+1);
	parent.resize(n+1);
	depth.resize(n+1);
	up.resize(n+1, vector<int>(20));
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	for (int i=0; i<n; i++) {
		parent[i]=i;
	}
	for (int i=0; i<n; i++)  {
		int u; cin >> u;
		pq.push({u, i});
	}
	for (int i=0; i<n-1; i++) {
		int u, v; cin >> u >> v;
		u--, v--;
		adjbase[u].push_back(v);
		adjbase[v].push_back(u);
	}
	initdfs(0);
	int last=0;
	while (!pq.empty()) {
		int s=pq.top().second; pq.pop();
		last=s;
		for (auto u: adjbase[s]) {
			unite(u, s);
		}
		already[s]=true;
	}
	cout << calcans(last) << endl;
	return;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
	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