START205——Water Supply

思路讲解

1. 单条边的传输关系是单调的
   对一条漏水系数为 w 的边，从上游输入 x，到下游得到 x - ⌊x/w⌋；这是关于 x 的非减函数。
   因而“想让下游至少得到 need”的逆运算也是单调：最小的上游输入 x 满足 x - ⌊x/w⌋ ≥ need。你代码里的 get(need, w) 就是在做这件事（通过二分求最小可行 x）。

2. 一次修边只能选择一条路径上的一条边
   每天只走“根→某个节点”的一条简单路径，因此修哪条边只会影响包含该边的那些路径。
   若我们要求所有**“弱点”节点**（即 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 的子树，而不是整棵树，所以可控。

2. 把 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

源代码

// 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……）