2025-ICPC-Asia-Taiwan-Online-台湾网络赛-J. Gas Station（贪心的关键是，找到最优子结构）（最优子结构是什么？就是在不在这贪取决于什么！）（每一颗子树都最小化加油站数量，再检测在最小化加油站数量前提下，是否违反了限制，强迫摆放加油站） · znzryb
## 题目大意
亚历克斯正在规划在一个简化的台湾高速公路系统模型上设立休息区。该系统包含$n$个互通立交，由$n-1$条双向道路连接。网络是连通的，任意一对互通立交之间有且仅有一条最短路径。第$i$条道路连接互通$u_i$和$v_i$，长度为$l_i$。
**可以建造恰好**$k$**个带加油站的休息区**，每个位于一个互通。司机可以从任意互通开始旅行到任何其他互通，始终沿着唯一最短路径。他们每次旅行都会带满油箱，只能在设有休息区的互通处加油。
亚历克斯想知道可能的**最小燃油箱容量**$d$，以便可以以一种方式放置这$k$个休息区，确保没有任何司机会耗尽燃油。在任何旅行中，司机永远不应该在沿途行驶超过$d$个单位而不经过休息区，包括旅程的开始或结束。目标是找出最小的$d$，假设休息区被以最佳方式放置。
## 思路讲解
[https://hackmd.io/@tmt514/Bk_lRqjill#Problem-J---Gas-Station](https://hackmd.io/@tmt514/Bk_lRqjill#Problem-J---Gas-Station)
::: 官方题解
## Problem J - Gas Station
觀察到如果選擇了一個比正確答案還要小的 $d'$，則需要的加油站數量會大於 $k$，反之小於等於 $k$。因此藉由二分搜尋法，透過指定的 $d'$ 計算所需要的加油站數量，來檢驗選定的 $d'$ 是太大或是太小。
對於計算加油站數量的部分，由於我們固定了 $d'$，因此可以簡單的使用 DFS 來計算。設 $\mathsf{dfs}(r)$ 為以 $r$ 為根的子樹，$r$ 到最近的加油站距離。對於 $r$ 的子樹 $(u, l)$，若
1. $l > d'$ 則明顯無解
1. $\mathsf{dfs}(u)+l>d'$ 則我們應設一個加油站在 $u$
最後，如果存在 $r$ 的兩個子樹 $(u, l_u)$, $(v, l_v)$ 他們之間加油站的距離 $\mathsf{dfs}(u)+l_u+l_v+\mathsf{dfs}(v) > d'$，則我們應設一個加油站在 $r$。
該 $\mathsf{dfs}$ 可以在 $O(n)$ 的時間完成，二分搜尋法檢驗的範圍不大於 $\sum l$，因此整體時間複雜度為 $O(n\log \sum l)$ 。
:::
说白了，只要**每一颗子树都最小化加油站数量**，然后我们**再检测在最小化加油站数量前提下，是否违反了限制**。
贪心的关键是，找到最优子结构。**最优子结构是什么？就是在不在这贪取决于什么！**
```cpp
auto dfs=[&](auto && self,ll u,ll p) -> ll {
ll dis=0;
ll plus=0;
for (auto [v,w]:g[u]) {
if (v==p) continue;
ll ldis=self(self,v,u);
ldis+=w;
// 如果说 ldis 本身就大于 d 这个门槛呢？那么给 v 节点加一个加油站
if (ldis>d_threshold) {
cnt_put++;
ldis=w;
}
// 如果说，ldis 和 最远子节点距离 (mx)dis 之间大于了 d 呢？
// 给 u 节点加一个加油站
if (ldis+dis>d_threshold) {
plus=1;
}
dis=max(dis,ldis);
}
cnt_put+=plus;
if (plus) {
return 0;
}
return dis;
};
```
## AC代码
AC
[https://codeforces.com/gym/106084/submission/361152548](https://codeforces.com/gym/106084/submission/361152548)
::: 源代码
```cpp
/**
* Problem: J. Gas Station
* Contest: 2025 ICPC Asia Taiwan Online Programming Contest
* Judge: Codeforces
* URL: https://codeforces.com/gym/106084/problem/J
* Created: 2026-02-02 18:55:51
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT;
/*
*
*/
void Solve() {
ll N,K;
cin >> N >> K;
vector<vector<pair<ll,ll>>> g(N+2);
ll sumw=0,mxw=0;
for (int i=1;i<=N-1;++i) {
ll u,v,w;
cin>>u>>v>>w;
sumw+=w;
mxw=max(mxw,w);
g[u].push_back({v,w});
g[v].push_back({u,w});
}
ll l=mxw,r=sumw;
ll cnt_put=0;
ll d_threshold=0;
auto dfs=[&](auto && self,ll u,ll p) -> ll {
ll dis=0;
ll plus=0;
for (auto [v,w]:g[u]) {
if (v==p) continue;
ll ldis=self(self,v,u);
ldis+=w;
if (ldis>d_threshold) {
cnt_put++;
ldis=w;
}
if (ldis+dis>d_threshold) {
plus=1;
}
dis=max(dis,ldis);
}
cnt_put+=plus;
if (plus) {
return 0;
}
return dis;
};
auto check=[&]() -> bool {
cnt_put=0;
dfs(dfs,1,-1);
if (cnt_put > K) {
return false;
}
return true;
};
while (l<r) {
ll mid=l+r>>1;
d_threshold=mid;
if (check()) {
r=mid;
}else {
l=mid+1;
}
}
cout<<l<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// cin >> lT;
// while(lT--)
Solve();
return 0;
}
/*
AC
https://codeforces.com/gym/106084/submission/361152548
*/
```
:::
## 心路历程（WA，TLE，MLE……）