这道题由于是当场做的,所以思考的比较完善一点,当时看完题就明确了这是一个贪心,一开始只写了把当前节点的人向子节点平摊,但是后来手模了一组数据发现不对劲。
因为最后要走到叶子结点为止,所以叶子结点多的子树平摊的潜力就更大,所以一路平摊下去就行。
其实打的时候很快就想出来了,但是不知道怎么想的,觉得有很多特判的点就写了好多种情况。
其实直接除下去分配掉就好了。
下附代码:
1 #include<cstdio> 2 #include<iostream> 3 #define ll long long 4 using namespace std; 5 int Next[2000005],tot=0,to[2000005],head[1000005],n; 6 ll y[1000005],ans=0; 7 ll a[1000005],sum[1000005]; 8 void add(int a,int b){ 9 Next[tot]=head[a],to[tot]=b; 10 head[a]=tot++; 11 } 12 void dfs(int x,int pre){ 13 sum[x]=a[x]; 14 for (int i=head[x]; i!=-1; i=Next[i]){ 15 int v=to[i]; 16 if (v!=pre){ 17 dfs(v,x); 18 sum[x]+=sum[v]; 19 } 20 } 21 ans=max(ans,(sum[x]+y[x]-1)/y[x]); 22 } 23 void find(int x,int pre){ 24 y[x]=0; 25 ll cnt=0; 26 for (int i=head[x]; i!=-1; i=Next[i]){ 27 int v=to[i]; 28 if (v!=pre){ 29 find(v,x); 30 cnt++; 31 y[x]+=y[v]; 32 } 33 } 34 if (cnt==0) y[x]=1; 35 } 36 int main(){ 37 scanf("%d",&n); 38 for (int i=1; i<=n; i++) head[i]=-1; 39 for (int i=2; i<=n; i++){ 40 int x; 41 scanf("%d",&x); 42 add(x,i); 43 add(i,x); 44 } 45 for (int i=1; i<=n; i++){ 46 scanf("%lld",&a[i]); 47 } 48 find(1,-1); 49 dfs(1,-1); 50 printf("%lld",ans); 51 return 0; 52 }