专栏文章

P13824 「Diligent-OI R2 D」在水一方 题解

PPlanetary_system
P13824题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mio6c8fv
此快照首次捕获于
2025/12/02 14:05
3 个月前
此快照最后确认于
2025/12/02 14:05
3 个月前
查看原文

事先声明：

文中树上距离指两点之间简单路径的长度，直接距离指「NC2 距离」，即欧几里得距离的平方。

题面解释：

nn 个节点一棵树，每次询问一个 dd，找到一个树上距离最大的点对 i,ji,j，使得在 i,ji,j 向上移动过程中，始终保持直接距离不超过 dd。

思路分析：

观察到 n=1000n=1000，极大可能是 O(n2log⁡n)O(n^2\log n) 的时间复杂度（后来的实践证明这是正确的）。
考虑枚举点对，如果已经预处理出树上距离以及两点所需要的最小的 dd，我们可以对点对依次按距离降序、ii 升序、jj 升序进行排序，对询问离线后按 dd 降序排序，只需要枚举点对即可得到答案。
那么先预处理两点树上距离。首先，i,ji,j 的树上简单路径为 i∼lcai\sim lca 与 j∼lcaj\sim lca 之和，所以我们只需要计录每个节点到根节点的树上距离，易得任意两点树上距离（此处本人使用倍增法求树上最近公共祖先）。
然后预处理两点所需最小的 dd，根据定义就是 i,ji,j 向上移动时直接距离的最小值。这里明显可以 DP 实现。定义 faifa_i 为 ii 的父节点，disi,jdis_{i,j} 为两点直接距离，dpi,jdp_{i,j} 意义如所求值。有：
dpi,j=max⁡(min⁡(dpfai,j,dpi,faj,dpfai,faj),disi,j)dp_{i,j}=\max(\min (dp_{fa_i,j},dp_{i,fa_j},dp_{fa_i,fa_j}),dis_{i,j})
由于实现时需保证父节点已完成转移，此处本人使用bfs转移（dfs应该也可行）。

AC Code:

赛时代码，实现十分丑陋，将就看吧。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1010;
int n,t,x[N],y[N],dis[N][N],mp[N][N],st[N][40];
int dep[N],lca[N][N],w[N],len[N][N],res[N*N];
bool vis[N][N];vector<int>g[N];
void dfs(int u,int fa){
	st[u][0]=fa,dep[u]=dep[fa]+1;
	w[u]=w[fa]+dis[u][fa];
	for(int v:g[u])
		if(v!=fa)dfs(v,u);
}

struct S{int len,u,v,d;}ans[N*N];
inline bool cmp(S p,S q){
	return(p.len^q.len?p.len>q.len:p.u^q.u?p.u<q.u:p.v<q.v);
}
struct node{int u,v,rt;};

struct qry{int val,id;}r[N*N];
inline bool cmp2(qry p,qry q){
	return p.val>q.val;
}
queue<node>q;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	cin>>n>>t;
	for(int i=1;i<=n;i++)
		cin>>x[i]>>y[i];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dis[i][j]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
	for(int i=1,u,v;i<n;i++)
		cin>>u>>v,
		g[u].push_back(v),
		g[v].push_back(u);
	dfs(1,1);
	for(int i=1;i<=30;i++)
		for(int j=1;j<=n;j++)
			st[j][i]=st[st[j][i-1]][i-1];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			int u=i,v=j;
			if(dep[u]<dep[v])swap(u,v);
			for(int i=30;i>=0;i--)
				if(dep[st[u][i]]>=dep[v])u=st[u][i];
			if(u==v){lca[i][j]=u;continue;}
			for(int i=30;i>=0;i--)
				if(st[u][i]!=st[v][i])
					u=st[u][i],v=st[v][i];
			lca[i][j]=st[u][0];
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			mp[i][j]=1000000000000000;
	for(int i=1;i<=n;i++)
		mp[i][i]=0,q.push({i,i,i});
	while(!q.empty()){
		int u=q.front().u,v=q.front().v,rt=q.front().rt;
		q.pop();
		for(int U:g[u])
			if(U!=st[u][0]&&lca[U][v]==rt){
				mp[U][v]=min(mp[U][v],max(mp[u][v],dis[U][v]));
				if(!vis[U][v])vis[U][v]=1,q.push({U,v,rt}); 
			}
		for(int V:g[v])
			if(V!=st[v][0]&&lca[u][V]==rt){
				mp[u][V]=min(mp[u][V],max(mp[u][v],dis[u][V]));
				if(!vis[u][V])vis[u][V]=1,q.push({u,V,rt}); 
			}
		for(int U:g[u])if(U!=st[u][0])
		for(int V:g[v])if(V!=st[v][0])
		if(lca[U][V]==rt){
			mp[U][V]=min(mp[U][V],max(mp[u][v],dis[U][V]));
			if(!vis[U][V])vis[U][V]=1,q.push({U,V,rt});
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			len[i][j]=w[i]+w[j]-2*w[lca[i][j]],
			ans[(i-1)*n+j]={len[i][j],i,j,mp[i][j]};
	sort(ans+1,ans+n*n+1,cmp);
	for(int i=1;i<=t;i++)cin>>r[i].val,r[i].id=i;
	sort(r+1,r+t+1,cmp2);
	int i=1,j=1;
	while(j<=t)
		if(ans[i].d<=r[j].val)res[r[j++].id]=i;
		else i++;
	for(int i=1;i<=t;i++)
		cout<<ans[res[i]].u<<' '<<ans[res[i]].v<<'\n';
	return 0;
}
完结撒花！！！

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...