题解 P9058【[Ynoi2004] rpmtdq】
cyffff
·
·
题解
\text{Link}
这题之前在 Ynoi 以强制在线、不带边权和 5\times 10^4 的数据范围作为一个 O(n\sqrt n) 题目出现过，这个是解法，后来被替换掉了。
现在它变成了 polylog 的题再次进入 Ynoi。
$\text{Upd2023.11.1}$：修正一处 $\min$ 写成 $\max$。
## 题意
给出一颗 $n$ 个点的有权树，$q$ 次询问，每次询问给出 $l,r$，求 $\displaystyle\min_{l\le i<j\le r}\text{dis}(i,j)$。允许离线。
$n\le 2\times 10^5$，$q\le 10^6$。
## 思路
最近点对问题有一个通用思路，就是找“支配点对”，也就是说，有许多的点对是没有用的。
由于树上距离涉及路径，我们可以思考点分治。对于一次分治，我们要思考这个连通块两两之间有哪些是会计入最终有效点对的。
考虑将连通块内所有点 $p$ 以二元组 $(p,a_p)$ 表示，其中 $a_p$ 表示 $\text{dis}(p,r)$，$r$ 为当前分治中心。则对于点对 $(p,q)$，我们有 $\text{dis}(p,q)\le a_p+a_q$。（为什么是 $\le$ 号？因为 $p,q$ 可能来自分治中心的同一个子树。但是这种情况我们无需特殊处理，默认 $\text{dis}(p,q)=a_p+a_q$，原因下文将给出）
我们考虑一下这层分治的有效点对 $(i,k)$，无效点对 $(i,j),(j,k)$，其中 $i<j<k$。对 $i$ 考虑 $(i,k)$ 有效相当于 $\text{dis}(i,j)>\text{dis}(i,k)$ 即 $a_j>a_k$，对 $k$ 有类似的 $a_j>a_i$，即 $a_i<a_j,a_k<a_j$。所以对于有效点对 $(l,r)$，$\max(a_l,a_r)<\displaystyle\min_{i=l+1}^{r-1}a_i$。
有一个想法是，按 $a_p$ 的值从小到大排序，初始时有一空集，依次向集合中加入对应的 $p$。设加入 $p$ 之前，集合里 $p$ 的前驱为 $v$、后继为 $w$，则 $(p,v)$ 和 $(p,w)$ 都是有效点对。容易用 `set` 维护。每个点在每个包含它的分治只会加入 $O(1)$ 组合法点对，则总合法点对数是 $O(n\log n)$ 的。
说一下不用管同子树的点对的影响的原因：同子树内的点对的距离只会更近，把距离放大了还比不过那就说明被淘汰掉的点对是无效的了。
考虑找出所有的合法点对 $(i,j),i<j$ 后怎么做，用扫描线，维护序列 $t$，扫到 $j$ 的时候 $t_i=\min(t_i,\text{dis}(i,j))$，扫到 $r$ 处理 $[l,r]$ 询问，即查询 $\displaystyle\min_{p=l}^r t_p$ 等价于单点取 $\min$ 后缀 $\min$，用树状数组即可搞定。
点分治部分每一层是 $O(s\log s)$ 的，总共是 $O(n\log^2n)$，扫描线有 $O(n\log n)$ 组修改和 $q$ 组查询，复杂度为 $O(n\log^2n+q\log n)$，总时间复杂度 $O(n\log ^2n+q\log n)$，空间复杂度 $O(n\log n+q)$。
但是这么写你会被卡常。
考虑优化找有效点对的过程，我们发现这个过程等价于按 $p$ 排序，维护 $a_p$ 的单调**不减**的单调栈，按 $p$ 顺序加入 $a_p$，在弹出栈顶所有大于 $a_p$ 的数后，设栈顶为 $a_v$，则 $(v,p)$ 为一对有效点对。我们正反做两遍即可。
时空复杂度不变。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
}
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define mpr make_pair
#define fir first
#define sec second
const int N=2e5+10,M=1e6+10,INF=1e9;
const ll INF_=1e18;
int n,q,head[N],cnt,siz[N],top;
bool del[N];
ll ans[M];
pil stk[N],stk2[N];
int top2;
vector<int>use[N];
struct Edge{
int to,nxt,w;
}a[N<<1];
struct Query{
int l,id;
};
vector<Query>qr[N];
inline void add(int u,int v,int w){
cnt++;
a[cnt].to=v;
a[cnt].nxt=head[u];
a[cnt].w=w;
head[u]=cnt;
}
inline void push(int u,int v){
if(u>v) swap(u,v);
use[v].emplace_back(u);
}
inline pii findroot(int rt,int f,int pre){
siz[rt]=1;
int mx=0;
pii ans=make_pair(INF,0);
for(int i=head[rt];i;i=a[i].nxt){
int t=a[i].to;
if(del[t]||t==f) continue;
ans=min(ans,findroot(t,rt,pre));
siz[rt]+=siz[t];
mx=max(mx,siz[t]);
}
ans=min(ans,mpr(max(mx,pre-siz[rt]),rt));
return ans;
}
inline void dfs(int rt,int f,ll s){
stk[++top]=mpr(rt,s);
for(int i=head[rt];i;i=a[i].nxt){
int t=a[i].to;
if(t==f||del[t]) continue;
dfs(t,rt,s+a[i].w);
}
}
inline void solve(int rt,int pre){
int root=findroot(rt,0,pre).second;
int res=siz[rt];
del[root]=1;
top=0;
for(int i=head[root];i;i=a[i].nxt){
int t=a[i].to;
if(del[t]) continue;
dfs(t,root,a[i].w);
}
stk[++top]=mpr(root,0);
sort(stk+1,stk+top+1);
top2=0;
for(int i=1;i<=top;i++){
int id=stk[i].fir;
ll d=stk[i].sec;
while(top2&&stk2[top2].sec>d) top2--;
push(id,stk2[top2].fir);
stk2[++top2]=stk[i];
}
top2=0;
for(int i=top;i>=1;i--){
int id=stk[i].fir;
ll d=stk[i].sec;
while(top2&&stk2[top2].sec>d) top2--;
push(id,stk2[top2].fir);
stk2[++top2]=stk[i];
}
for(int i=head[root];i;i=a[i].nxt){
int t=a[i].to;
if(del[t]) continue;
solve(t,res);
}
}
struct ST_table{
int dep[N],ind[N],lg[N<<1],cnt,st[20][N<<1];
ll de[N];
inline void dfs(int rt,int f){
dep[rt]=dep[f]+1;
st[0][++cnt]=rt,ind[rt]=cnt;
for(int i=head[rt];i;i=a[i].nxt){
int t=a[i].to;
if(t==f) continue;
de[t]=de[rt]+a[i].w;
dfs(t,rt);
st[0][++cnt]=rt;
}
}
inline int cmp(int x,int y){
return dep[x]<dep[y]?x:y;
}
inline void init(){
dfs(1,0);
for(int i=1;(1<<i)<=cnt;i++)
for(int j=1;j+(1<<i)-1<=cnt;j++)
st[i][j]=cmp(st[i-1][j],st[i-1][j+(1<<i-1)]);
for(int i=2;i<=cnt;i++)
lg[i]=lg[i>>1]+1;
}
inline int LCA(int x,int y){
x=ind[x],y=ind[y];
if(x>y) swap(x,y);
int i=lg[y-x+1];
int p=1<<i;
return cmp(st[i][x],st[i][y-p+1]);
}
inline ll dis(int x,int y){
return de[x]+de[y]-2*de[LCA(x,y)];
}
}s;
struct BIT{
#define lowbit(i) (i&-i)
ll t[N];
inline void init(){
for(int i=1;i<=n;i++)
t[i]=INF_;
}
inline void add(int p,ll v){
for(int i=p;i;i-=lowbit(i))
t[i]=min(t[i],v);
}
inline ll query(int p){
ll ans=INF_;
for(int i=p;i<=n;i+=lowbit(i))
ans=min(ans,t[i]);
return ans;
}
}T;
int main(){
n=read();
for(int i=1;i<n;i++){
int u=read(),v=read(),w=read();
add(u,v,w),add(v,u,w);
}
solve(1,n);
s.init();
T.init();
q=read();
for(int i=1;i<=q;i++){
int l=read(),r=read();
if(l>=r) ans[i]=-1;
else qr[r].emplace_back((Query){l,i});
}
for(int i=1;i<=n;i++){
sort(use[i].begin(),use[i].end());
use[i].resize(unique(use[i].begin(),use[i].end())-use[i].begin());
}
for(int i=1;i<=n;i++){
for(auto t:use[i])
T.add(t,s.dis(t,i));
for(auto t:qr[i])
ans[t.id]=T.query(t.l);
}
for(int i=1;i<=q;i++)
write(ans[i]),putc('\n');
flush();
}
```