D. Bandit in a City(DFS + 叶子节点数目)

Problem - 1436D - Codeforces

 

输出标准输出
城市里出现了强盗! 他们中的一个正试图尽可能多地抓捕市民。

这个城市由n个广场组成，由n-1条道路连接，从任何其他广场都可以到达任何广场。1号广场是主广场。

星期天散步后，所有的道路都改为单行道，这样就有可能从主广场到达任何一个广场。

当强盗出现在主广场的时候，第i个广场上有ai个公民。现在，以下过程将开始。首先，每个目前在有一些出城单行道的广场上的公民选择其中一条道路，并沿着它移动到另一个广场。然后，强盗选择一条从他所在的广场发出的单行道，并沿着它移动。这个过程重复进行，直到强盗位于一个没有出城道路的广场。匪徒抓住了该广场上的所有公民。

匪徒想抓尽可能多的市民；市民则想尽量减少被抓的人数。匪徒和公民在任何时候都知道所有公民的位置，公民可以合作。如果双方都采取最佳行动，将有多少公民被抓？

输入
第一行包含一个整数n--城市中的方块数（2≤n≤2⋅105）。

第二行包含n-1个整数p2,p3...pn，意味着从广场pi到广场i有一条单行道（1≤pi

第三行包含n个整数a1,a2,...,an--最初每个广场上的公民数量（0≤ai≤109）。

输出
打印一个整数--如果双方都采取最佳行动，强盗将捕获的公民数量。

例子
输入
3
1 1
3 1 2
输出
3
输入
3
1 1
3 1 3
输出
4
注意
在第一个例子中，1号方格的公民可以分成2+1两组，因此2号和3号方格将各有3名公民。

在第二个例子中，无论公民如何行动，强盗至少可以抓到4个公民。

题解:
根据题意我们可以发现,强盗只能从一棵子树的根部,不断往下遍历,不可往回走,同样,公民也无法往回走,但是公民可以向他所在的子树分配公民,使强盗抓到的人最少,要想抓到的人最少,肯定会不断平均往下分配公民,导致最终的结果就是,一个子树的sum[i]/子树叶子节点数量son[i]

分配公民时存在两种情况

1.如果存在一个儿子v,使得就算不给v分配一个居民,最后还是v子树内的叶子节点居民最大,那么就把问题规模缩小成以v为根的子树了(其他儿子就没用了)

2.如果不存在这种儿子v ,就存在一种分配方式使得所有叶子节点尽量平均

最终所有的情况一最后都变成了情况二

由于强盗也同样聪明,最后肯定会找遍历途中最大的

#include<iostream>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cstring>
#include<stack>
using namespace std;
long long s[200050];
long long son[200050];
long long a[200050];
vector<int> p[200050];
void dfs(int u)
{
	int f = 0;
	s[u] = a[u];
	for(int i = 0;i < p[u].size();i++)
	{
		int j = p[u][i];
		dfs(j);
		f = 1;
		son[u] += son[j];
		s[u] += s[j]; 
	}
	if(!f)
	son[u] = 1;
}
void solve()
{
	int n;
	cin >> n;
	for(int i = 2;i <= n;i++)
	{
		int x;
		cin >> x;
		p[x].push_back(i);
	}
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i];
	}
	dfs(1);
	long long ans = 0;
	for(int i = 1;i <= n;i++)
	{
		ans = max(ans,s[i]/son[i]+(s[i]%son[i]!=0));
	}
	cout<<ans;
}
int main()
{
	int t = 1;
//	cin >> t;
	while(t--)
	{
		solve();
	}
}
//
//abcdef
//babcdef
//1110011
 
//