D. Bandit in a City
给出一个n个点n-1条边的有向树(n<2e5)
每个点有一些居民 ,他们可以选择一条出边进行移动(或留在原地)
晚上强盗从1号点出发,一直走到不能移动
强盗想抓到更多的人，而居民则不想让他抓到更多的人
问最后强盗能抓到多少人
参考题解
若所有居民都在1号点 那么显然最后强盗能抓到最多=round up(total/leaves)
即总人数/叶子结点上取整人数
但是这么做存在问题：有的居民不能从当前的点走到1号点再平均分配
由于这个问题 某些点的子树中居民人数较多那么最后强盗抓到的人数会比
假设所有居民都从1号点出发要多
因为一旦假设的平均值需要这个子树上的居民到1号点(实际则不能到1号点)
再分配给所有叶子结点
说明这以这个点为根的子树人数更多 就算不给它分配一个居民,最后还是它子树内的叶
子节点居民数最大,那么就把问题规模缩小成以这个点为根的子树了(其他儿子就没用了)
如果不存在这种子节点,就存在一种分配方式使得两边尽量平均
此时在以u为根的子树内最大的叶子节点就是$roundup(sum_u/leaves_u)$
所以最终答案是最大的$roundup(sum_u/leaves_u)$ 值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
#define P pair<ll,ll>
const int Max=2e5+5;
const int Mod=1e9+7;
const int inf=0x3f3f3f3f;
ll num[Max];
ll leaves[Max],sz[Max],maxn=0;
bool vis[Max];
vector<int>mp[Max];
void dfs(int now){
sz[now]=num[now];
if(mp[now].empty())leaves[now]=1;
for(auto to:mp[now]){
dfs(to);
sz[now]+=sz[to];
leaves[now]+=leaves[to];
}
ll di=sz[now]%leaves[now]?1:0;
maxn=max(maxn,sz[now]/leaves[now]+di);
}
int main(){
Turnoff;
int n;cin>>n;
for(int i=2;i<=n;i++){
int u,v=i;cin>>u;
mp[u].push_back(v);
}
for(int i=1;i<=n;i++)cin>>num[i];
dfs(1);
cout<<maxn<<endl;
}
|