题意

给定一棵树形结构，每个点上都有一定的人数，人只能往叶子节点跑，根节点有一个土匪，问土匪最少能抓到多少人。

分析

我们只需要让所有的人均匀地跑到叶子节点就可以了，因此对于每个节点都有一个最优方案，也就是当前子树人数/当前子树叶子节点数+(人数%叶子节点 ? 1 : 0)，最后取一个max就可以了，比较水的一道题。

AC Code

#include 
   
    #define ACM_LOCAL#define fi first#define se second#define pb push_backusing namespace std;typedef long long ll;typedef pair
    
      PII;const int N = 5e5 + 10, M = 5e5 + 10, INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;int n, m, k, cnt;ll sz[N], ans[N], a[N], res;vector
     
       g[N];void dfs(int u) {       ans[u] = a[u];    if (g[u].empty()) sz[u] = 1;    for (auto v : g[u]) {           dfs(v);        sz[u] += sz[v];        ans[u] += ans[v];    }}void count(int u) {       res = max(res, ans[u] / sz[u] + (ans[u] % sz[u] ? 1 : 0));    for (auto v : g[u]) {           count(v);    }}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);    cout.tie(0);#ifdef ACM_LOCAL    freopen("input", "r", stdin);    freopen("output", "w", stdout);#endif    solve();    return 0;}

转载地址：http://qlcoz.baihongyu.com/

你可能感兴趣的文章