START205——Water Supply · znzryb
## 思路讲解
1. **单条边的传输关系是单调的**
对一条漏水系数为 w 的边，从上游输入 x，到下游得到 `x - ⌊x/w⌋`；这是关于 x 的非减函数。
因而“想让下游至少得到 need”的**逆运算**也是单调：最小的上游输入 x 满足 `x - ⌊x/w⌋ ≥ need`。你代码里的 `get(need, w)` 就是在做这件事（通过二分求最小可行 x）。
1. **一次修边只能选择一条路径上的一条边**
每天只走“根→某个节点”的一条简单路径，因此修哪条边只会影响包含该边的那些路径。
若我们要求所有**“弱点”节点**（即 R[u] < 目标值 mid 的节点）都至少收到 mid，那么被修的那条边必须同时位于它们各自的从根到该点路径上。
这些路径的**公共部分**正是 `根→(所有弱点的 LCA)` 的路径。所以：
> 必要条件：可行的被修边一定在 root → anc 这条路径上，其中 anc 是所有 R[u]<mid 的节点的 LCA。
1. **把“树下游的要求”折算为“对 anc 入水量的要求”**
如果我们暂时不修边，问：“从 anc 向下，把整棵以 anc 为根的子树都喂到 ≥ mid，需要 anc 处至少有多少输入？”
由于每条边的传输是单调的，这个“所需的 anc 输入量”是单调的，可以二分出最小可行值 `need_at_anc`。
你用 `dfs2(anc, candidate, mid)` 来判定“给 anc 值为 candidate 时，子树是否都 ≥ mid”，并对 candidate 二分拿到最小的 `need_at_anc`。这一步只会遍历 **anc 的子树**，而不是整棵树，所以可控。
1. **把 anc 的需求一路往上折算，看是否能借“修一条边”满足**
假设我们已经知道：只要 anc 处能拿到至少 `need_at_anc` 的输入，它子树就都 OK。
现在看 `root → anc` 这条路径。我们在这条路径上自下而上地**把需求往上游推**：
- 当前在节点 `node` 处需要 `need`；让 `fa=node 的父亲`，边权 `w=A[node]`。
- 若**修边**选在 `(fa,node)` 上，则 node 能直接拿到 `R[fa]`（因为这条边不再漏水）。于是只要 `R[fa] ≥ need` 就已经满足了——这就是你代码里的“**只要某一层祖先的** **`R[ancestor] ≥ need`****，我们就能在这个祖先与其子之间修边，一步到位**”的判定。
- 否则，如果暂时不修这条边，就要通过这条漏水边把 `need` 推到父亲处，父亲的**所需输入**变为 `get(need, w)`。继续往上迭代，直到找到某个祖先 `y` 满足 `R[y] ≥ 当前 need`，那么在 `(y, its child)` 修边即可；若最终到根也没有成功，则该 mid 不可行。
这正是你 `check(mid)` 的核心：
- 先找弱点集合 `wp = { i | R[i] < mid }`，若空则已可行。
- 把 `anc = LCA(wp 所有点)`。
- 对 `anc` 的所需输入二分最小可行 `need_at_anc`（用 `dfs2` 验证）。
- 把 `need_at_anc` 沿 `anc→root` 方向往上折算：
- 若某处祖先的**原始** `R[ancestor] ≥ 当前 need` → 可在它与子之间修边，成功；
- 否则用 `get(need, w)` 把需求继续往上推；
- 推到顶都不行则失败。
于是，**一次修边能否让所有点 ≥ mid** 被转换为上述流程的一个布尔判断。
## AC代码
AC
[https://www.codechef.com/viewsolution/1194966856](https://www.codechef.com/viewsolution/1194966856)
::: 源代码
```cpp
// by Gospel_rock
#include <bits/stdc++.h>
#include <vector>
#define all(vec) vec.begin(), vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var << ":" << var << "\n";
#define cend cerr << "\n-----------\n"
#define fsp(x) fixed << setprecision(x)
#define minn(vec) *min_element(vec.begin(), vec.end())
#define maxx(vec) *max_element(vec.begin(), vec.end())
#define yyy cout << "YES\n"
#define nnn cout << "NO\n"
using namespace std;
#ifdef LOCAL
template <typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template <typename T> void _print(vector<T> v) {
cerr << "[ ";
for (T i : v)
_print(i), cerr << " ";
cerr << "]";
}
template <typename T> void _print(set<T> s) {
cerr << "{ ";
for (T i : s)
_print(i), cerr << " ";
cerr << "}";
}
template <typename T, typename U> void _print(pair<T, U> p) {
cerr << "{";
_print(p.first);
cerr << ", ";
_print(p.second);
cerr << "}";
}
template <typename T, typename U> void _print(map<T, U> m) {
cerr << "{ ";
for (auto &p : m)
_print(p), cerr << " ";
cerr << "}";
}
// 打印两层数组，格式好一些
template <typename T> void _print(vector<vector<T>> v) {
cerr << "{\n";
for (auto i : v)
_print(i), cerr << "\n";
cerr << " }";
}
#endif
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using pdd = pair<DB, DB>;
using plb = pair<ll, bool>;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vb = vector<bool>;
using tll = tuple<ll, ll, ll>;
using vii = vector<int>;
using vpll = vector<pll>;
using vtll = vector<tll>;
using vdb = vector<DB>;
using vc = vector<char>;
using arr3 = array<ll, 3>;
using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)2e5 + 10,
INF = (ll)1e17 + 3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = (ll)1e9 + 7; // 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;
struct Solve {
vector<vector<arr2>> g;
vector<arr2> edge;
vll R;
vll Dep;
ll op(ll a, ll b) {
if (Dep[a] <= Dep[b]) {
return a;
}
return b;
}
vll fa;
Solve() {
cin >> N >> K;
g.resize(N + 5);
edge.resize(N + 5);
Dep.resize(N + 5);
in.resize(N + 5);
fa.resize(N + 5);
R.resize(N+5);
fa[1]=1;
FOR(i, 2, N) {
cin >> edge[i][0];
fa[i] = edge[i][0];
}
FOR(i, 2, N) { cin >> edge[i][1]; }
FOR(i, 2, N) {
auto [p, w] = edge[i];
g[p].PB({i, w});
g[i].PB({p,w});
}
dfs(1, K,1);
st.resize(__lg(SZ(eu)) + 5, vll(SZ(eu) + 5));
FOR(i, 0, SZ(eu) - 1) { st[0][i] = eu[i]; }
FOR(i, 1, __lg(SZ(eu))) {
FOR(j, 0, SZ(eu) - (1 << i) + 1 - 1) {
st[i][j] = op(st[i - 1][j], st[i - 1][j + (1ll << (i - 1))]);
}
}
ll mn = INF;
FOR(i, 1, N) { mn = min(mn, R[i]); }
ll l = mn, r = K;
while (l < r) {
ll mid = l + r + 1 >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
cout << l << "\n";
}
bool check(ll mid) {
vll wp;
FOR(i, 1, N) {
if (R[i] < mid) {
wp.PB(i);
}
}
if(wp.empty()) return true;
ll anc = wp[0];
FOR(i, 1, SZ(wp) - 1) { anc = query(anc, wp[i]); }
ll l = R[anc], r = K;
ll check;
while (l < r) {
ll mid2 = l + r >> 1;
if (check2(anc, mid2, mid)) {
r = mid2;
} else {
l = mid2 + 1;
}
}
if (l == K) {
if (!check2(anc, l, mid)) {
return false;
}
}
ll node = anc, need = l;
if (R[anc] >= need)
return true;
while (node != 1) {
if (R[fa[node]] >= need) {
return true;
}
ll w = edge[node][1];
need = get(need, w);
if (need == -1)
return false;
node = fa[node];
}
return false;
}
ll get(ll need, ll w) {
ll l = 0, r = K;
while (l < r) {
ll mid = l + r >> 1;
if (mid - mid / w >= need) {
r = mid;
} else {
l = mid + 1;
}
}
if (l - l / w < need)
return -1;
return l;
}
int dfs2(ll u, ll wat, ll lim,ll pa) {
ll dfs;
if (wat < lim) {
return 0;
}
int ret = 1;
for (auto [v, w] : g[u]) {
if(v==pa) continue;;
ret &= dfs2(v, wat - wat / w, lim,u);
if (ret == 0)
return ret;
}
return ret;
}
bool check2(ll anc, ll mid, ll lim) { return dfs2(anc, mid, lim,fa[anc]); }
ll query(ll u, ll v) {
ll l = in[u], r = in[v];
if (l > r)
swap(l, r);
ll k = __lg(r - l + 1);
ll res = op(st[k][l], st[k][r - (1ll << k) + 1]);
return res;
}
vll in;
ll tot = 0;
vll eu;
vector<vll> st;
void dfs(ll u, ll wat,ll pa) {
R[u] = wat;
in[u] = tot;
++tot;
eu.PB(u);
for (auto [v, w] : g[u]) {
if(v==pa) continue;
Dep[v] = Dep[u] + 1;
dfs(v, wat - wat / w,u);
++tot;
eu.PB(u);
}
}
};
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> lT;
while (lT--)
Solve a;
return 0;
}
/*
AC
https://www.codechef.com/viewsolution/1194966856
*/
```
:::
## 心路历程（WA，TLE，MLE……）