洛谷 P10838 庭中有奇树

题目传送门

思路

这道题乍一看是一个博弈论的题，但其实稍微想想可以发现，如果小 G 能开挂，肯定就尽量开挂，当然如果走树边的答案比开挂更优，那就走树边，还有注意如果这两种情况都大于了 \(1e9\)，那么直接强制开挂即可。

因为只能开挂一次，所以预处理 S 和 T 点到所有点的距离，记为 \(dis_{s,i}\) 和 \(dis_{t,i}\) 那么小 G 所需的金币数量就是 \(dis_{s,i}+dis_{t,j}+k\) 当然得满足 \(i,j\) 不相邻。因为小 Y 很正义，所以他就需要把上面这个式子中的前 \(m\) 小封印掉，那么其实最终答案就是第 \(m\) 小的 \(dis_{s,i}+dis_{t,j}+k\)

这个的话，其实就是经典的 \(a_{i}+b_{j}\) 的第 \(k\) 大的问题，将 \(a\) 或者 \(b\) 排序，然后二分答案即可。假如当前枚举的答案是 \(val\)，设比 \(val\) 小的 \(dis_{s,i}+dis_{t,j}+k\) 的数量为 \(cnt\)，那么当 \(m\le cnt\) 时，\(r=mid\)，否则 \(l=mid+1\)，求 \(cnt\) 的话，枚举每一个 \(dis_{s,i}\)，在 \(dis_{t,i}\) 上二分找到小于等于 \(val-dis_{s,i}\) 的数量，全部加起来就是 \(cnt\)。
注意在这道题中 \(i,j\) 不能相邻，所以 \(cnt\) 再减去相邻的多统计了的即可。

时间复杂度 \(O(n\log n \log V)\)。

代码

// Problem: P10838 『FLA - I』庭中有奇树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10838
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,m,s,t,k,K,head[MAXN],dis[2][MAXN],Dis[MAXN];
bool vis[MAXN];
struct node{
    int to,next,val;
}edge[MAXN<<1];

void build(int u,int v,int w){
    edge[++K].to=v;
    edge[K].next=head[u];
    edge[K].val=w;
    head[u]=K;
}

void dfs(int u,int f){
    vis[u]=true;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(vis[v]) continue;
        dis[f==t][v]=dis[f==t][u]+edge[i].val;
        dfs(v,f);
    }
}

int chk(int val){
    int sum=0;
    for(int i=1;i<=n;i++){
        int z=val-dis[0][i];
        int pos=upper_bound(Dis+1,Dis+n+1,z)-Dis-1;
        sum+=pos;
        for(int j=head[i];j;j=edge[j].next){
            int v=edge[j].to;
            if(dis[0][i]+dis[1][v]<=val) sum--;
        }
    }
    // cout<<val<<" "<<sum<<endl;
    return sum;
}

signed main(){
    read(n,m,k,s,t);
    for(int i=1;i<n;i++){
        int u,v,w;
        read(u,v,w);
        build(u,v,w);
        build(v,u,w);
    }
    dfs(s,s);
    for(int i=1;i<=n;i++) vis[i]=false;
    dfs(t,t);
    for(int i=1;i<=n;i++) Dis[i]=dis[1][i];
    sort(Dis+1,Dis+n+1);
    // for(int i=1;i<=n;i++) cout<<dis[0][i]<<" "<<dis[1][i]<<endl;
    int l=0,r=1e9;m++;
    while(l<r){
        int mid=(l+r)>>1;
        if(chk(mid)>=m) r=mid;
        else l=mid+1;
    }
    cout<<min({dis[0][t],l+k,1000000000ll});
    return 0;
}