LGP10838 [FLA R1] 庭中有奇树 学习笔记
\(\texttt{Luogu Link}\)
前言
时隔一年。
题意简述
给定一个有边权的无根树，大小为 \(n\)。
小 \(\texttt{G}\) 要从 \(s\) 走到 \(t\)，但是他有一次开挂机会，允许以 \(k\) 的代价在 \((x,y)\) 间连一条单向边。
小 \(\texttt{Y}\) 超级生气暴怒，所以他可以指定 \(m\) 个点对 \((x,y)\)，使得小 \(\texttt{G}\) 在这些 \((x,y)\) 间连单向边的代价变为 \(10^9\)。特别规定，\((x,y)\) 在原树上不能有边相连。
两边都足够聪明，小 \(\texttt{Y}\) 希望最大化最终小 \(\texttt{G}\) 的行动代价，而小 \(\texttt{G}\) 则希望最小化自己的行动代价。小 \(\texttt{G}\) 可以看到小 \(\texttt{Y}\) 封锁的路线。问最终行动代价是多少。
\(2\le n\le 10^5\)，\(0\le m,k\le 10^9\)，\(1\le w_i\le 10^9\)，\(s\neq t\)。
做法解析
呃首先这个开挂只是多连一次单向边而已。所以实际上最终代价的组成方式结构也是简单的。就三类：
- 不开挂。代价为 \(\text{dis}(s,t)\)。
- 我就直接开挂那咋了。直接从 \(s\) 传送到 \(t\)，代价为 \(10^9\)。若 \(m=0\) 则代价为 \(k\)。
- 我们开挂是吃操作的要意识的。代价为 \(k+\text{dis}(s,x)+\text{dis}(y,t)\)，其中 \((x,y)\) 是满足 \(\text{dis}(s,x)+\text{dis}(y,t)\) 第 \(m+1\) 小的。因为 \((x,y)\) 只有 \((n-1)^2\) 个，所以若 \(m\ge (n-1)^2\) 则无需考虑。
\(\text{dis}(s,t)\) 通过 \(\texttt{DFS}\) 就求出来了。那么 \((x,y)\) 怎么找呢？答案是找不到。可我们也不关心 \((x,y)\) 本身，我们实际上只关心第 \(m+1\) 大的 \(\text{dis}(s,x)+\text{dis}(y,t)\) 的长度。这不是我们的 \(\texttt{LGP1631}\) 吗？
不是。因为 \(m\) 可以是 \(O(n^2)\) 的，你不能真的做一遍 \(\texttt{LGP1631}\)。正确的做法是二分这个长度，对于每次二分的值 \(lim\)，你用双指针来求有多少 \(\text{dis}(s,x)+\text{dis}(y,t)\le lim\)，如果有不少于 \(m+1\) 个，那实际的答案就不大于 \(lim\)。
复杂度 \(O(n\log V)\)。
代码实现
#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=1e5+5;
const lolo I=1e9;
lolo N,M,K,S,T,X,Y,Z;
vector<pii> Tr[MaxN];
void addudge(int u,int v,int w){Tr[u].push_back({v,w});Tr[v].push_back({u,w});
}
lolo sdis[MaxN],tdis[MaxN];
void dfs(int u,int f,lolo dis[]){for(auto [v,w] : Tr[u])if(v!=f)dis[v]=dis[u]+w,dfs(v,u,dis);}
pli sdp[MaxN],tdp[MaxN];
bool check(lolo lim){lolo cnt=0;for(int p=1,q=N;p<=N;p++){auto [ppw,ppu]=sdp[p];for(;q&&ppw+tdp[q].first>lim;q--);cnt+=q;for(auto [v,w] : Tr[ppu])if(tdis[v]+ppw<=lim)cnt--;}return cnt>M;
}
lolo ans;
int main(){readis(N,M,K,S,T);for(int i=1;i<N;i++)readis(X,Y,Z),addudge(X,Y,Z);dfs(S,0,sdis),dfs(T,0,tdis);ans=sdis[T];if(!M){minner(ans,K),writi(ans);return 0;}minner(ans,I);if(M>=(N-1)*(N-1)){writi(ans);return 0;}for(int i=1;i<=N;i++)sdp[i]={sdis[i],i},tdp[i]={tdis[i],i};sort(sdp+1,sdp+N+1),sort(tdp+1,tdp+N+1);lolo sl=1,sr=I-1,smid,sres=I;while(sl<=sr){smid=(sl+sr)>>1;if(check(smid))sres=smid,sr=smid-1;else sl=smid+1;}minner(ans,sres+K);writi(ans);return 0;
}