题面

第三题 流水线
提交文件: line.cpp
输入文件: line.in
输出文件: line.out
时间空间限制： 2 秒, 256 MB
在计算机组成原理这门课中，小明的老师布置了实现 CPU 流水线的作业。小明打算设计出一个效率最
高的流水线。简单来说，流水线就是将 CPU 分成若干个任务模块，而一个模块又可以继续划分成更小的模
块，小模块可以划分成更小的小小模块……根据常识我们知道把一个任务划分后，每一个部分的代价会变少，
但是可能会产生额外的代价。所以小明希望你帮助他解决这个问题。
我们可以用一棵以 1 为根的有根树来描述模块之间的关系，每个节点是一个模块，每个节点的点权对应
着该模块的时间代价。每一个非叶子节点可以划分成该节点的儿子节点对应的模块。
每个模块都有一定的时间代价，而流水线最后的效率我们可以用划分的模块数乘上模块中时间代价最大
的一个来表示，时间代价越小，流水线的效率越高。也就是说，假如小明最后把 CPU 划分为了 m 个模块，每
个模块的代价为 w1, w2, · · · , wm，则总代价为 m · max(w1, w2, · · · , wm)。另外，我们认为根节点对应的模块
不往下划分模块也是一种合法的方案。
请你帮小明找到效率最高的流水线设计方案吧
输入格式
第一行一个正整数 n，表示模块对应有根树的节点个数。
第二行 n 个整数，表示 n 个模块的时间代价 wi。
第三行 n − 1 个数 fi（2 ≤ i ≤ n），表示节点 2, · · · , n 在有根树中的父节点。保证给出的是一棵以 1 为
根的树。
输出格式
一个整数 T，表示最小的时间代价。
样例数据
line.in line.out
5
10 7 3 3 2
1 1 2 2
9
样例解释
样例中将模块 1 拆分为模块 2 和模块 3，再将模块 2 拆分为模块 4 和模块 5，代价为 3 · 3 = 9。
数据范围
对于所有测试点，1 ≤ n ≤ 105，0 ≤ wi ≤ 109，wi ≤ wfi。

这题考场乱搞贪心搞出来一个100pts的做法，求正确性证明或HACK

#include<cstdio>
#include<vector>
#define int long long
using namespace std;
const int maxn=1e5+10;
struct node{
	int size,cmxv,bv,csize;
	bool flag;
	vector<int> ch;
}tree[maxn];
int n;
void dfs(int u){
	tree[u].flag=0;
	for(int i=0;i<tree[u].ch.size();i++){
		int v=tree[u].ch[i];
		dfs(v);
		if(tree[v].flag==1){
			tree[u].cmxv=max(tree[u].cmxv,tree[v].cmxv);
			tree[u].csize+=tree[v].csize;
		}
		else{
			tree[u].cmxv=max(tree[u].cmxv,tree[v].bv);
			tree[u].csize++;
		}
	}
	int mx=0;
	for(int i=0;i<tree[u].ch.size();i++){
		int v=tree[u].ch[i];
		mx=max(tree[v].bv,mx);
	}
	if(tree[u].ch.size()!=0&&tree[u].cmxv*tree[u].csize>mx*tree[u].ch.size()){
		tree[u].csize=tree[u].ch.size();tree[u].cmxv=mx;
	}
	if((tree[u].bv>tree[u].cmxv*tree[u].csize)&&tree[u].ch.size()!=0) tree[u].flag=1;
}
signed main(){
	freopen("line.in","r",stdin);
	freopen("line.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&tree[i].bv);
	for(int i=2;i<=n;i++){
		int fa;
		scanf("%lld",&fa);
		tree[fa].ch.push_back(i);
	}
	dfs(1);
	printf("%lld",min(tree[1].bv,tree[1].csize*tree[1].cmxv));
	fclose(stdin);
	fclose(stdout);
	return 0;
}
/*
7
10 4 3 3 3 3 3
1 1 2 2 3 3

5
10 9 4 5 6
1 2 3 4

8
100 4 4 1 1 1 2 1
1 1 2 2 2 3 3
*/