codeforces D. Bandit in a City

题目链接：https://codeforces.ml/contest/1436/problem/D

题意：最开始强盗在1，然后1可以到每个点（n-1条单边），每个点最开始有ai个人.人可以沿着路径向下跑，问强盗最终最少可以追到多少个人（强盗和人都很聪明）。

题解：dfs一遍sum[i]表示每个节点为根节点的子树的总权，zs[i]表示以该节点为根的子树有多少个叶子。

最终只需要求出最大的sum[i]/zs[i]+(sum[i]%zs[i])?0:1;就ok了。

代码：

#include <bits/stdc++.h>

#define ll long long
#define pi acos(-1)
#define pb push_back
#define mst(a, i) memset(a, i, sizeof(a))
#define pll pair<ll, ll>
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define dbg(x) cout << #x << "===" << x << endl
using namespace std;
template<class T>void read(T &x){T res=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){res=(res<<3)+(res<<1)+c-'0';c=getchar();}x=res*f;}
void print(ll x){if(x<0){putchar('-');x=-x;}if(x>9)print(x/10);putchar(x%10+'0');}
const ll maxn = 2e5 + 10;
const ll mod = 1e9 + 7;

ll n,p,a[maxn],sum[maxn],zs[maxn],mx[maxn],du[maxn];
vector<ll> g[maxn];
bool f=false;
void dfs(ll x,ll fa){
    for(auto i:g[x]){
        if(i==fa) continue;
        dfs(i,x); 
        sum[x]+=sum[i];
        zs[x]+=zs[i];
        mx[x]=max(mx[x],mx[i]);
    }
}

//ll gcd(ll a,ll b){return (b==0)?a:gcd(b,a%b);}
//ll qpow(ll a,ll p,ll mod){ll ans=1;a=a%mod;while(p){if(p&1)ans=(ans*a)%mod;p>>=1;a=(a*a)%mod;}return ans;}
int main() {
    ll _s = 1;
    //read(_s);
    for (ll _=1;_<=_s;_++) {
        read(n);
        for(ll i=2;i<=n;i++){
            read(p);
            g[p].pb(i);
            du[p]++;
        }
        for(ll i=1;i<=n;i++) read(a[i]);
        for(ll i=1;i<=n;i++){
            if(du[i]==0) zs[i]=1,mx[i]=a[i];
            sum[i]=a[i];
        }
        dfs(1,-1);
        /*
        for(ll i=1;i<=n;i++){
            printf("zs[%lld]=%lld,mx[%lld]=%lld,sum[%lld]=%lld\n",i,zs[i],i,mx[i],i,sum[i]);
        }*/
        //?好像mx没有必要
        ll ans=0;
        for(ll i=1;i<=n;i++){
            ll t=(sum[i]%zs[i]==0)?0:1;
            ll c=sum[i]/zs[i]+t;
            ans=max(ans,c);
        }
        cout<<ans;
    }
    return 0;
}
/*
input:::
6 
1 2 3 2 1
5 2 7 6 4 1
output:::

*/

//哭了，队友说不难，果然不难，玛德一直卡c题去了，玛德，我也是个人才。我现在，应该养成认真的习惯！！！认真对待比赛，争取在赛场上将所有水平都发挥出来。

//我可能是简单题做多了，遇到难题就害怕emmm

本文地址：https://blog.csdn.net/I_have_a_world/article/details/109269701