题目
给你一棵有根的树，由 𝑛n 个顶点组成。树中的顶点编号为 11 至 𝑛n ，根顶点为 11 。值 𝑎𝑖ai 写在第 𝑖i 个顶点上。
您可以执行以下任意次数(可能为零)的操作：选择一个顶点 𝑣v **该顶点至少有一个子顶点。至少有一个子顶点；将 𝑎𝑣av 增加 11 ；并将 𝑎𝑢au 减少 11 ，所有顶点 𝑢u 都在 𝑣v 的子树中( 𝑣v 本身除外)。但是，每次操作后，所有顶点上的值都应该是非负值。
您的任务是通过上述操作计算出写入根的最大可能值。
输入
第一行包含一个整数 𝑡t ( 1≤𝑡≤1041≤t≤104 ) - 测试用例数。
每个测试用例的第一行包含一个整数 𝑛n ( 2≤𝑛≤2⋅1052≤n≤2⋅105 ) - 树中顶点的数量。
第二行包含 𝑛n 个整数 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an ( 0≤𝑎𝑖≤1090≤ai≤109 ) - 写入顶点的初始值。
第三行包含 𝑛−1n−1 个整数 𝑝2,𝑝3,…,𝑝𝑛p2,p3,…,pn ( 1≤𝑝𝑖≤𝑛1≤pi≤n )，其中 𝑝𝑖pi 是树中第 𝑖i 个顶点的父节点。顶点 11 是根。
输入的附加限制：所有测试用例中 𝑛n 的总和不超过 2⋅1052⋅105 。
输出
对于每个测试用例，打印一个整数--使用上述操作在根处写入的最大可能值。
做法
#include<bits/stdc++.h>
using namespace std;
int t,n;
long long a[200010];
vector<int> g[200010];
void dfs(int x){
long long mi=1e9+10;
for(auto y:g[x]){
dfs(y);
mi=min(mi,a[y]);//子树的最小值
}
if(mi!=1e9+10){ //底部值不变 （没有子树）
if(mi>a[x]){
a[x]=(mi+a[x])/2;///最多增加
}
else a[x]=mi;//最多增加
}
}
int main(){
cin>>t;
while(t--){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=2;i<=n;i++){
int p;
scanf("%d",&p);
g[p].push_back(i);
}
long long f=a[1];
dfs(1);
long long mi=2e9+10;
for(auto x: g[1]){
mi=min(mi,a[x]);//最多能增加的值
}
cout<<mi+f<<endl;
for(int i=1;i<=n;i++) g[i].clear();
}
}