P10838 『FLA - I』庭中有奇树

前言

本题解较为基础，推导如何得出二分解题思路。

题目大意

给出无根带权树，双方采取最佳策略，求节点S->T的最短路。

有两种操作：

• 我方至多可以使用一次传送，花费k元从a传送到b（ab不能相邻）。
• 敌方至多可以把m条道路的传送消耗设置为1e9元（单向设置，如设置a->b消耗不影响b->a）。

思路

显然的，答案可以分两种情况。

不使用传送

对方的操作不用看，答案直接S->T的最短路。

使用传送

设传送起点为u，传送终点为v。总体流程为S->u然后传送到v然后v->T。

别忘了此处u，v不能相邻。

$$disS[i]$$为i距起点距离，$$disT[i]$$为i距终点距离。答案即$$disS[u]+k+disT[v]$$。

通过$$dfs$$预处理，我们可以在$$O(n)$$得出$$disS$$和$$disT$$。

使用传送的情况下，还可以再细分出两种答案。

通过对手限制的道路

消耗都是$$1e9$$，所以传送越早越好。答案就是$$1e9$$。

如果S和T相邻的话，因为边权$$<=1e9$$，最后答案取min不会造成问题。

不通过对手限制的道路

不妨先试举几个m。

如果对方的m为0，那么答案就是最小的$$(disS[u]+disT[v])$$然后+k。

如果对方的m为1，那么答案就是第二小的$$(disS[u]+disT[v])$$然后+k。

朴素的想法是，暴力求出所有u,v的可能组合，其中的第m+1小$$(disS[u]+disT[v])+k$$就是答案。但是复杂度到达$$n^2$$，会tle。

直接寻找第k小显然超时。我们可以反向思考另一个问题：给出一个数字x，x在是第几小？如果能在$$O(nlogn)$$的级别以内解决这个新问题，我们只需要再套上$$O(logv)$$二分即可获得答案。

此处反向思考是经典的第k小问题。给出例题

如何解决新问题？

我们枚举u，即固定了$$dis[u]$$，只需要获取所有满足$$disS[u]+disT[v]<=x$$即$$disT[v]<=x-disS[u]$$。

我们可以提前维护一个升序的$$disT$$，再进行一次二分即可获得答案。总复杂度是$$O(nlogn)$$的

此处需注意u，v不能相邻。在得到答案后，

还需枚举u的邻边y，如果$$disS[u]+disT[y]<=x$$答案需减一。

以及考虑$$disS[u]+disT[u]<=x$$

总结

现在我们有三部分答案

1. 不使用传送，即$$disT[S]$$
2. 使用传送，并通过对手设置路段，即1e9
3. 使用传送，并不通过对手设置路段，即二分出的x

三者最小即为答案。

代码如下

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll N = 1e5 + 5;
int n, m, k, S, T;
vector<pll> e[N];
ll disS[N], disT[N]; //距起点和终点的距离
ll tmp[N];           //维护升序的disT用来二分
void dfs(int u, int fa, ll *dis) {for (auto &[v, w] : e[u]) {if (v == fa) continue;dis[v] = dis[u] + w;dfs(v, u, dis);}
}
bool check(ll x) {ll sum = 0;for (int u = 1; u <= n; u++) {sum += upper_bound(tmp + 1, tmp + 1 + n, x - disS[u]) - tmp - 1;for (auto &[v, w] : e[u]) { //邻边if (disS[u] + disT[v] <= x) sum--;}if (disS[u] + disT[u] <= x) sum--; //自身}return sum > m;
}
void solve() {cin >> n >> m >> k >> S >> T;for (int i = 1; i < n; i++) {int u, v, w;cin >> u >> v >> w;e[u].push_back({v, w});e[v].push_back({u, w});}dfs(S, 0, disS);dfs(T, 0, disT);for (int i = 1; i <= n; i++) tmp[i] = disT[i];sort(tmp + 1, tmp + 1 + n);ll l = 0, r = 1e18;while (l <= r) {ll mid = l + (r - l) / 2;if (check(mid)) {r = mid - 1;} else {l = mid + 1;}}cout << min({l + k, (ll)1e9, disT[S]}) << endl;
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);solve();return 0;
}