Submission #1174780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174780		Tsagana	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	187 ms	57616 KiB

Main

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

struct DSU {
	int P[200010];
	void prep() {
		for (int i = 1; i <= 200000; i++) P[i] = i;
	}

	int find(int x) {return x == P[x] ? x : P[x] = find(P[x]);}

	void merge(int x, int y) {
		x = find(x);
		y = find(y);
		P[x] = P[y];
	}
} U;

struct GRAPH {
	int vis[200010];
	int lvl[200010];
	int J[200010][20];
	vector<int> adj[200010];

	void connect(int x, int y) {
		adj[x].pb(y);
		adj[y].pb(x);
	}

	void start() {
		J[1][0] = 1;
		lvl[1] = 0;
		dfs(1);
	}

	void dfs(int s) {
		for (int i = 1; i <= 18; i++) J[s][i] = J[J[s][i-1]][i-1];
		vis[s] = 1;
		for (auto i: adj[s]) {
			if (vis[i]) continue ;
			lvl[i] = lvl[s] + 1;
			J[i][0] = s;
			dfs(i);
		}
	}

	int jump(int x, int k) {
		for (int i = 17; i >= 0; i--) {
			if (k & (1 << i)) x = J[x][i];
		}
		return x;
	}
	
	int LCA(int x, int y) {
		if (lvl[x] < lvl[y]) swap(x, y);
		x = jump(x, lvl[x] - lvl[y]);
		if (x == y) return x;
		for (int i = 18; i >= 0; i--) {
			if (J[x][i] == J[y][i]) continue ;
			x = J[x][i];
			y = J[y][i];
		}
		return J[x][0];
	}

	int calc(int x, int y) {
		int k = LCA(x, y);
		return lvl[x] + lvl[y] - 2 * lvl[k];
	}
} G;

void solve() {
	int n;
	cin >> n;

	vector<int> h(n);
	for (auto &i: h) cin >> i;

	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		x = h[x-1];
		y = h[y-1];
		G.connect(x, y);
	}

	G.start();
	U.prep();

	int ans = 0;
	vector<int> mx(n+1, 0);

	for (int i = 1; i <= n; i++) {
		for (auto j: G.adj[i]) {
			if (j > i) continue ;
			int x = U.find(j);
			mx[i] = max(mx[i], mx[x] + G.calc(i, x));
			U.merge(x, i);
		}
		ans = max(ans, mx[i]);
	}

	cout << ans << '\n';
}
signed main() {IOS 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