P13824 「Diligent-OI R2 D」在水一方 题解
Planetary_system
·
·
题解
事先声明：
文中树上距离指两点之间简单路径的长度，直接距离指「NC2 距离」，即欧几里得距离的平方。
题面解释：
## 思路分析：
观察到 $n=1000$，极大可能是 $O(n^2\log n)$ 的时间复杂度（后来的实践证明这是正确的）。
考虑枚举点对，如果已经预处理出树上距离以及两点所需要的最小的 $d$，我们可以对点对依次按距离降序、$i$ 升序、$j$ 升序进行排序，对询问离线后按 $d$ 降序排序，只需要枚举点对即可得到答案。
那么先预处理两点树上距离。首先，$i,j$ 的树上简单路径为 $i\sim lca$ 与 $j\sim lca$ 之和，所以我们只需要计录每个节点到根节点的树上距离，易得任意两点树上距离（此处本人使用倍增法求树上最近公共祖先）。
然后预处理两点所需最小的 $d$，根据定义就是 $i,j$ 向上移动时直接距离的最小值。这里明显可以 `DP` 实现。定义 $fa_i$ 为 $i$ 的父节点，$dis_{i,j}$ 为两点直接距离，$dp_{i,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;
}
```
完结撒花！！！