NOIP2023模拟7联测28 距离

本文主要是介绍NOIP2023模拟7联测28 距离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

给一棵 $n$ 个节点的无根树，每条边都有一个边权 $w_i$ 。令 $d i s (x, y)$ 为点 $x$ 到点 $y$ 的距离。

你需要维护一个初始为空的点对集合 $S$ ，有 $m$ 次操作，每次操作有两种类型：

1 a b往 $S$ 中插入点对 $(a, b)$
2 x y查询下面的式子并输出结果
$\min\limits_{(a,b)\in S}dis(x,a)+dis(y,b)$

若查询时 $S$ 为空，则输出 $- 1$ 。

$1\leq n,m\leq 2\times 10^5,1\leq w_i\leq 10^9$

在子任务 $2$ 中， $b = 1$ 。

时间限制 $4000 m s$ ，空间限制 $512 MB$ 。

题解

首先，我们考虑子任务 $2$ ，此时相当于点对变成了但单个点。问题就变成了每次往点集插入一个点，或者询问距离某个点最近的点的距离。

考虑用点分树，在每个重心维护其点分树内距离重心最近的点即可，修改和查询时不断往上跳即可。时间复杂度为 $O(n\log n)$ 。

下面考虑如何处理点对的情况。

我们可以将所有操作都离线下来，将 $a_i$ 和 $x_i$ 进行点分治，在每一层点分治中处理所有 $a_i$ 和 $x_i$ 在其点分治子树中的操作。设当前的分治中心为点 $u$ ，则按时间顺序在另一棵点分树上插入 $b_i$ ，并加上 $dis(u,a_i)$ ，查询时就使用使用普通点分树的操作查询即可（也就是不断往上跳）。

每次修改和查询会在点分治中的 $O(\log n)$ 个点中体现，每次体现都要在点分树上 $O(\log n)$ 来进行修改和查询，所以总时间复杂度为 $O(m\log^2n)$ 。

可以参考代码帮助理解。

code

#include<bits/stdc++.h>
using namespace std;
const int N=200000;
int n,m,fl=0,root,rt=0,tot=0,d[2*N+5],l[2*N+5],r[N+5];
int siz[N+5],mxd[N+5],z[N+5],fa[N+5],dw[N+5];
long long w[2*N+5],mn[N+5],ans[N+5],dis[N+5][20];
struct que{int op,x,y;
}q[N+5];
vector<int>G[N+5],id[N+5];
void add(int xx,int yy,int zz){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;w[tot]=zz;
}
void dfs(int u,int fa,int all,int dw){siz[u]=1;mxd[u]=0;mn[u]=1e18;for(int i=r[u];i;i=l[i]){if(d[i]==fa||z[d[i]]) continue;dis[d[i]][dw]=dis[u][dw]+w[i];dfs(d[i],u,all,dw);siz[u]+=siz[d[i]];mxd[u]=max(mxd[u],siz[d[i]]);}mxd[u]=max(mxd[u],all-siz[u]);if(mxd[u]<mxd[rt]) rt=u;
}
void dd(int u){z[u]=1;for(int i=r[u];i;i=l[i]){if(z[d[i]]) continue;rt=0;dis[d[i]][dw[u]]=w[i];dfs(d[i],0,siz[d[i]],dw[u]);G[u].push_back(rt);fa[rt]=u;dw[rt]=dw[u]+1;dd(rt);}
}
void pt(int x,long long v){for(int tx=x;tx;tx=fa[tx]){mn[tx]=min(mn[tx],v+dis[x][dw[tx]]);}
}
long long gt(int x){long long re=1e18;for(int tx=x;tx;tx=fa[tx]){re=min(re,mn[tx]+dis[x][dw[tx]]);}return re;
}
void clr(int x){for(int tx=x;tx;tx=fa[tx]) mn[tx]=1e18;
}
void solve(int u){for(int i:id[u]){if(q[i].op==1) pt(q[i].y,dis[q[i].x][dw[u]]);else ans[i]=min(ans[i],gt(q[i].y)+dis[q[i].x][dw[u]]);}for(int i:id[u]){if(q[i].op==1) clr(q[i].y);}for(int v:G[u]) solve(v);
}
int main()
{freopen("distance.in","r",stdin);freopen("distance.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1,x,y,z;i<n;i++){scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}for(int i=1;i<=m;i++){scanf("%d%d%d",&q[i].op,&q[i].x,&q[i].y);ans[i]=1e18;}mxd[0]=1e9;dfs(1,0,n,0);root=rt;dw[root]=1;dd(root);for(int i=1;i<=m;i++){for(int u=q[i].x;u;u=fa[u]) id[u].push_back(i);}solve(root);for(int i=1;i<=m;i++){if(q[i].op==1) fl=1;else{if(!fl) printf("-1\n");else printf("%lld\n",ans[i]);}}return 0;
}