D. Maximize the Root

题意

题目链接
给一棵树，每个点初始权值给定，对每一棵树，根节点每增加1，所有叶子节点减少1，问1号（根节点）最大权值多少

思路

1. 根节点加1，所有叶子节点减少1，那么操作次数就取决于子树中的最小值
2. 那么我们就可以维护子树中的最小值，并且让这个最小值最大
3. 用 表示这棵子树中最小值的最大值，也就是最终要存的答案
4. 用 存子树中的最小值
5. 那么有如下的分类讨论 :
   • < 时 这时操作会使得结果更差，不要
   • >= 时， 这时最小值变成了mp(s), 可以让他变大，变为

代码

#include <bits/stdc++.h>
#define endl '\n'
//#define int long long
using lli = long long;
using ull = unsigned long long;
typedef std::pair<int, int> pair;
typedef std::unordered_map<int, int> intmap;
typedef std::unordered_map<char, int> charmap;
//int ans = 0;
int val[200002] = {0};
std::vector<int> tree[200002];
std::unordered_map<int, int> mp;

void dfs(int s, int fa)
{
    //val[s] = mp[s];
    //std::cout << "s = " << s << endl;
    //std::cout << val[s] << endl;
    int tmp = 0x7f7f7f7f;
    for (int i = 0; i < tree[s].size(); i++)
    {
        int son = tree[s][i];
        if (son == fa) continue;
        dfs(son, s);
        tmp = std::min(tmp, val[son]);
        //std::cout << " tmp = " <<tmp << " ";
    }
    if (tmp == 0x7f7f7f7f)
    {
        val[s] = mp[s];
        return;
    }
    if (s == 1)
    {
        mp[s] += tmp;
        return;
    }
    if (tmp > mp[s])
    {
        val[s] = (mp[s] + tmp) / 2;
    }
    else
    {
        val[s] = tmp;
    }
}

void solve()
{
    //ans = 0;
    int n = 0, v = 0, s = 0;
    std::cin >> n;
    for (int i = 1; i <= n; i++)
    {
        tree[i].clear();
        val[i] = 0;
    }
    mp.clear();
    for (int i = 1; i <= n; i++)
    {
        std::cin >> v;
        mp[i] = v;
    }
    for (int i = 2; i <= n; i++)
    {
        std::cin >> s;
        tree[s].push_back(i);
        tree[i].push_back(s);
    }
    dfs(1, 0);
    std::cout << mp[1] << endl;
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t = 1;
    std::cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}