Educational Codeforces Round 168 (Rated for Div. 2) D. Maximize the Root
D. Maximize the Root
time limit per test: 3 seconds
memory limit per test: 256 megabytes
You are given a rooted tree, consisting of n vertices. The vertices in the tree are numbered from 1 to n, and the root is the vertex 1. The value aiai is written at the i-th vertex.
You can perform the following operation any number of times (possibly zero): choose a vertex v which has at least one child; increase avav by 1; and decrease au by 1 for all vertices u that are in the subtree of v (except v itself). However, after each operation, the values on all vertices should be non-negative.
Your task is to calculate the maximum possible value written at the root using the aforementioned operation.
Input
The first line contains a single integer t (1≤t≤10^4) — the number of test cases.
The first line of each test case contains a single integer n (2≤n≤2⋅10^5) — the number of vertices in the tree.
The second line contains n integers a1,a2,…,an (0≤ai≤10^9) — the initial values written at vertices.
The third line contains n−1 integers p2,p3,…,pn (1≤pi≤n), where pipi is the parent of the i-th vertex in the tree. Vertex 1 is the root.
Additional constraint on the input: the sum of n over all test cases doesn't exceed 2⋅10^5.
Output
For each test case, print a single integer — the maximum possible value written at the root using the aforementioned operation.
Example
Input
3
4
0 1 0 2
1 1 3
2
3 0
1
5
2 5 3 9 6
3 1 5 2
Output
1 3 6
Note
In the first test case, the following sequence of operations is possible:
- perform the operation on v=3, then the values on the vertices will be [0,1,1,1];
- perform the operation on v=1, then the values on the vertices will be [1,0,0,0].
【思路分析】
题意简化:给你一颗有根、含点权树,可以对任意节点进行任意次以下操作:子树所有节点点权-1,子树根结点点权+1。求操作后,该树根节点点权最大值。
贪心+树形dp。先考虑整体最优,显然根节点点权的最大值取决于其子树点权的最小值;再考虑局部最优,由于只能对根节点点权+1,仅当根节点点权比其所有子节点点权小时需要贪心地进行操作,操作结果为根节点点权和其子节点点权最小值取平均(向下取整)。
由于从叶子结点向上操作是无后效性的,显然做树形dp,dp[i]表示以编号i为根节点的子树中所有点权的最小值。
#include<bits/stdc++.h>
#define i64 long long
using namespace std;
const int N = 2e5 + 5;
vector<i64> E[N];
i64 a[N];
void dfs(i64 pos) {
if (E[pos].empty()) return;
i64 minn = LLONG_MAX / 2;
for (const auto &item: E[pos]) {
dfs(item);
minn = min(minn, a[item]);
}
if (a[pos] < minn) a[pos] = (minn + a[pos]) / 2;
else a[pos] = minn;
}
void solve() {
i64 n;
cin >> n;
for (int i = 1; i <= n; ++i) E[i].clear();
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 2; i <= n; ++i) {
i64 tmp;
cin >> tmp;
E[tmp].emplace_back(i);
}
i64 fi = a[1];
dfs(1);
i64 res = LLONG_MAX / 2;
for (const auto &item: E[1]) {
res = min(a[item], res);
}
cout << fi + res << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
上一篇: 归并排序
下一篇: 稳定扩散绘画:LoRA 模型验收