F

注意到，各个企鹅追与被追的关系可以抽象成基环树森林，我们使用并查集将森林分为多个基环树，每个基环树单独处理。
可以发现，知道当被追的企鹅停止时间，便可以得知追的企鹅的停止时间，具体计算公式如下:
当两只企鹅同向而行：t[i]=t[tar(i)]+dist
当两只企鹅相向而行：
if(dist[i]>=t[tar(i)])：t[i]=( dist - t[tar(i)] ) * 2 + t[tar(i)]
else:t[i]=dist
观察基环树可以想到，只要知道第一只在环中停下的企鹅停止时间，就可以推出树中所有企鹅的停止时间
如何找第一只停下的企鹅？贪心找到环内相向而行的企鹅中的相对距离最近的企鹅就是第一只停下的企鹅。
然后可以使用bfs来求解

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll = long long;
const ll N = 5e5 + 9;
typedef pair<ll,ll> pi;
struct Eg{
	ll u,v,d,dir;
};
ll s[N];
void init(ll n)
{
	for(ll i=1;i<=n;i++)
	s[i]=i;
}
ll find(ll x)
{
	if(x!=s[x])
	s[x]=find(s[x]);
	return s[x];
}

void solve()
{
	ll n;
	cin>>n;
	init(n);
	vector<ll> tar(n+10);
	vector<vector<ll>> from(n+10);
	vector<ll> pos(n+10);
	vector<Eg> eg(n+10);
	vector<ll> deg(n+10);
	for(ll i=1;i<=n;i++)
	{
		ll v;
		cin>>v;
		tar[i]=v;
		deg[v]++;
		from[v].push_back(i);
		ll fi=find(i),fv=find(v);
		if(fi!=fv)
		s[fi]=fv;
	}
	for(ll i=1;i<=n;i++)
		cin>>pos[i];
	for(ll i=1;i<=n;i++)
	{
		ll dir;
		if (pos[tar[i]] > pos[i])
		dir=1;
		else if (pos[tar[i]] < pos[i])
		dir=0;
		else
		dir=2;
		eg[i] = {i, tar[i], abs(pos[tar[i]] - pos[i]),dir};
	}
	vector<ll> ans(n+10),st2(n+10);
	vector<vector<ll>> g(n+10);
	for(ll i=1;i<=n;i++)
		g[find(i)].push_back(i);
	function<vector<ll>(vector<ll>&)> top=[&](vector<ll> &g){
		queue<ll> q;
		for(ll v:g)
		{
			if(deg[v]==0)
			q.push(v);
		}
		// cout<<q.size()<<endl;
		while(q.size())
		{
			ll t=q.front();
			q.pop();
			deg[tar[t]]--;
			if(deg[tar[t]]==0)
			q.push(tar[t]);
		}
		vector<ll> ans;
		for(ll v:g)
		if(deg[v]>0)
		ans.push_back(v);
		return ans;
	};
	function<void(vector<ll>&)> check=[&](vector<ll> &vc1){
		vector<ll> cir=top(vc1);
		pi s={1e18,0};
		for(ll v:cir)
		{
			if(eg[v].dir==eg[tar[v]].dir&&eg[v].dir!=2)
			continue;
			if(eg[v].d<s.x)
			s={eg[v].d,v};
		}
		queue<ll> q;
		q.push(s.y);
		st2[s.y]=true;
		ans[s.y]=eg[s.y].d;
		while (q.size())
		{
			ll v = q.front();
			q.pop();
			for (ll u : from[v])
			{
				if (st2[u])
					continue;
				ll t1 = ans[v];
				if (eg[u].dir == 2)
				{
					ans[u] = 0;
					q.push(u);
					st2[u] = 1;
				}
				else if (eg[u].dir == eg[v].dir) // 方向相同
				{
					ans[u] = t1 + eg[u].d * 2;
					q.push(u);
					st2[u] = 1;
				}
				else
				{
					ll d;
					if (t1 <= eg[u].d)
					{
						d = eg[u].d - t1;
						ans[u] = t1 + d * 2;
					}
					else
					{
						ans[u] = eg[u].d;
					}
					q.push(u);
					st2[u] = 1;
				}
			}
		}
		
	};
	for(ll i=1;i<=n;i++)
	if(find(i)==i)
	check(g[i]);
	for(ll i=1;i<=n;i++)
	cout<<ans[i]<<" ";
}
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ll t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

I

注意到lca(u,v)=a[u][v]^a[1][u]^a[1][v]，根据这个式子推断出每个节点的祖先，按照祖先->后代的关系建边，构成有向无环图，通过拓扑排序构造出一棵树

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll = long long;
const ll N = 5e5 + 9;
typedef pair<ll,ll> pi;
vector<ll> ne[N];
bool st[N];
void solve()
{
	ll n;
	cin>>n;
	vector<vector<ll>> a(n+10,vector<ll>(n+10));
	vector<ll> deg(n+10);
	for(ll i=1;i<=n;i++)
	{
		for(ll j=i;j<=n;j++)
		{
			cin>>a[i][j];
			a[j][i]=a[i][j];
			ll lc=a[1][i]^a[1][j]^a[i][j];
			if(i==j||lc>n||lc<1)
			continue;
			if(lc==i)
				ne[lc].push_back(j),deg[j]++;
			else if(lc==j)
				ne[lc].push_back(i),deg[i]++;
			else
			{
				ne[lc].push_back(i);
				ne[lc].push_back(j);
				deg[i]++,deg[j]++;
			}
		}
	}
	queue<ll> q;
	for(ll i=1;i<=n;i++)
	if(deg[i]==0)
	q.push(i);
	while(q.size())
	{
		ll u=q.front();
		q.pop();
		vector<ll> son;
		for(ll v:ne[u])
		{
			if(st[v])
			continue;
			
			deg[v]--;
			if(deg[v]==0)
			{
				q.push(v);
				cout<<u<<" "<<v<<endl;
			}
		}
	}
	
}
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ll t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}