本文共 1947 字，大约阅读时间需要 6 分钟。
好的，现在我来详细解释一下这个问题是如何解决的。
首先，我们需要理解题意：给定一棵树形结构，每个点上都有一定的人数，人只能向叶子节点移动，问土匪最少能抓到多少人。这个问题实际上涉及到如何在遍历每一个节点时，将人数合理分配到下一层的叶子节点，从而使得土匪能抓到的最少最大值最小化。
问题分析每个节点的人数需要合理分配到它所有的叶子节点。这样，每个叶子节点的人数不会过于拥挤，从而土匪在选择任何一条路径时，都能抓到尽可能少的最大人数。
递归方法我们可以使用递归的方法来计算每个节点如何分配人数。从叶子节点开始，计算各个祖先节点应该如何分配人数，使得每个子树的叶子节点的人数达到均衡。
分配策略对于每个节点，其人数应该被分配到每个子树中的叶子节点，分配的方式是基于子树的叶子数量来决定的。这样，每个叶子节点得到的人数会均匀一些，从而土匪分配的人数能够被最小化。
动态计算从叶子节点向上计算，每个节点要将自己的总人数分配给所有叶子节点所在的子树。这需要计算子树的大小，并根据子树的人数和叶子节点的数量来进行分配。
递归函数设计
dfs(u) 为计算节点 u 的总人数。sz[u] 表示节点 u 所在子树的总人数。ans[u] 表示节点 u 的最优解决方案。递归过程
u 无子树（即叶子节点），则 sz[u] = 1，ans[u] = a[u]（即该节点自身的人数）。dfs(v) 对于所有子节点 v，然后累加 sz 和 ans。v 子树中的叶子节点，使得每个叶子节点的 ans[v] 达到最大值。分配计算
u，计算其每个子树节点 v 的总人数 sz[v]。ans[v]。v 的叶子数量 outs。floor(current / outs) 和 current % outs 中的最大值。g[u] 用于存储节点 u 的所有子树。a[u] 表示节点 u 的初始人数。sz[u] 和 ans[u] 分别用于划分子树人数和计算最优抓取数量。#includeusing namespace std;void dfs(int u) { if (g[u].empty()) { sz[u] = 1; ans[u] = a[u]; return; } sz[u] = 1; ans[u] = 0; for (int v : g[u]) { dfs(v); sz[u] += sz[v]; ans[u] += ans[v]; }}void count(int u) { int outs = 0; ll total = ans[u]; for (int v : g[u]) { if (sz[v] == 1) { outs++; } count(v); } if (outs == 0) { return; } res = max(res, (total / outs) + (total % outs ? 1 : 0));}void solve() { int n; cin >> n; for (int i = 2; i <= n; i++) { int x; cin >> x; g[x].push_back(i); } for (int i = 1; i <= n; i++) { cin >> a[i]; } dfs(1); count(1); cout << res << endl;}int main() { ios_base::sync_with_stdio(false); cin.tie(0); solve(); return 0;}
通过递归的方法，我们从叶子节点开始计算每个节点的最优抓取方案，从而实现分配人数的最优化，这样土匪在根节点能够抓到最少的最大人数。代码中 dfs 函数计算每个节点的子树人数和最优解，count 函数则从根节点对所有可能的路径进行统计，最终得到 res，即土匪最少能抓到的最多人数。这个方法确保了计算的效率和正确性，能够处理大规模的树结构问题。
转载地址：http://qlcoz.baihongyu.com/