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
上一篇: 字符串哈希模板+例题
推荐阅读
-
Codeforces Round #482 (Div. 2) D. Kuro and GCD and XOR and SUM(数学+01字典树)(好题)
-
Codeforces Round #FF (Div. 2) D. DZY Loves Modification 贪心+优先队列_html/css_WEB-ITnose
-
Codeforces486 D. Valid Sets(树形dp,去重技巧)
-
Codeforces Round #656 (Div. 3)D. a-Good String(递归+dfs)
-
Educational Codeforces Round 97 (Rated for Div. 2) D. Minimal Height Tree
-
Codeforces Round #665 (Div. 2) D. Maximum Distributed Tree(dfs)
-
Codeforces Round #619 (Div. 2) D. Time to Run
-
Codeforces Round #583 (Div. 1 + Div. 2,) D. Treasure Island(dfs+思维)
-
[codeforces]round670 D. Three Sequences
-
Codeforces(D. 505)状压DP