题目
给你一棵有根的树,由 𝑛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();}
}