欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

codeforces D. Bandit in a City

程序员文章站 2022-03-27 16:03:15
题目链接: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

题目链接: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

相关标签: 图论