Submission #802774

#	Time	Username	Problem	Language	Result	Execution time	Memory
802774		starchan	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	237 ms	69896 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define LOGM (int)18
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
vector<int> pa(MX, -1);
vector<int> woke(MX);

int leader(int u)
{
	if(pa[u] < 0)
		return u;
	else
		return pa[u] = leader(pa[u]);
}
void merge(int u, int v)
{
	u = leader(u);
	v = leader(v);
	if(u==v)
		return;
	if(pa[u] < pa[v])
		swap(u, v);
	pa[v]+=pa[u];
	woke[v] = max(woke[v], woke[u]);
	pa[u] = v;
	return;
}

vector<int> adj[MX];
int timer;
int lca[LOGM][MX];
vector<int> st(MX), en(MX), dep(MX);
void DFS(int u, int p, int lvl)
{
	lca[0][u] = p;
	st[u] = timer++;
	dep[u] = lvl;
	for(int v: adj[u])
	{
		if(v==p)
			continue;
		DFS(v, u, lvl+1);
	}
	en[u] = timer;
}
int lcaa(int u, int v)
{	
	if(dep[u] > dep[v])
		swap(u, v);
	if((st[u] <= st[v]) && (en[v] <= en[u]))
		return u;
	for(int i = LOGM-1; i >= 0; i--)
	{
		int k = lca[i][u];
		if((st[k] <= st[v]) && (en[v] <= en[k]))
			continue;
		u = k;
	}
	return lca[0][u];
}
int dist(int u, int v)
{
	return dep[u]+dep[v]-2*dep[lcaa(u, v)];
}
signed main()
{
	fast();
	int n;
	cin >> n;
	vector<int> a(n+1);
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	int m = n-1;
	while(m--)
	{
		int u, v;
		cin >> u >> v;
		adj[a[u]].pb(a[v]);
		adj[a[v]].pb(a[u]);
	}
	DFS(1, 1, 0);
	for(int i = 1; i < LOGM; i++)
	{
		for(int u = 1; u <= n; u++)
			lca[i][u] = lca[i-1][lca[i-1][u]];
	}
	vector<int> dp(n+1, 0);
	woke[1] = 1;
	for(int u = 2; u <= n; u++)
	{
		woke[u] = u;
		for(int v: adj[u])
		{
			if(v > u)
				continue;
			dp[u] = max(dp[u], dp[woke[leader(v)]]+dist(u, woke[leader(v)]));
			merge(u, v);
		}
	}
	cout << dp[n] << "\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