Submission #74771261

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define minsort(x) sort(x.begin(), x.end())
#define maxsort(x) sort(x.begin(), x.end(), [](auto a, auto b) -> bool { return a > b; })
#define forn(i, x) for (auto i = 0; i < x; i++)
#define norf(i, x) for (auto i = x - 1; i >= 0; i--)
#define fore(x) for (auto &v : x)
#define pb push_back
#define lb(_name, _element) lower_bound(_name.begin(), _name.end(), _element)
#define ub(_name, _element) upper_bound(_name.begin(), _name.end(), _element)
#define IN_MAX 0x7fffffff
#define IN_MIN 0x80000001
#define LL_MAX 0x7fffffffffffffff
#define LL_MIN 0x8000000000000001
/*
    AC 喜欢！
    WA 不喜欢！
    TLE 不喜欢！
    MLE 不喜欢！
    RTE 不喜欢！
*/
#define int long long
void dfs(int n, vector<vector<int>> &graph, vector<int> &dp, vector<int> &num)
{
    dp[n] += num[n];
    for (auto next : graph[n])
    {
        dfs(next, graph, dp, num);
        dp[n] += dp[next];
    }
}
void dfs2(int n, vector<vector<int>> &graph, vector<int> &s, vector<int> &dp)
{
    if (graph[n].size() < 2)
        dp[n] = 0;
    else
    {
        int smax = -1;
        int smin = LL_MAX;
        for (auto next : graph[n])
        {
            smin = min(smin, s[next]);
            smax = max(smax, s[next]);
        }
        dp[n] = smax - smin;
    }
    for (auto next : graph[n])
    {
        dfs2(next, graph, s, dp);
    }
}
void solve()
{
    int n;
    cin >> n;
    vector<vector<int>> graph(n + 1);
    vector<int> num(n + 1);
    for (int i = 2; i <= n; i++)
    {
        int p;
        cin >> p;
        graph[p].pb(i);
    }
    for (int i = 1; i <= n; i++)
        cin >> num[i];
    vector<int> s(n + 1);
    vector<int> dp(n + 1);
    dfs(1, graph, s, num);
    dfs2(1, graph, s, dp);
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, dp[i]);
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    //    cin>>t;
    while (t--)
        solve();
    return 0;
}

Submission Info

Judge Result