Submission #1170012

#TimeUsernameProblemLanguageResultExecution timeMemory
1170012antonnMagic Tree (CEOI19_magictree)C++20
0 / 100
33 ms7876 KiB
#include <bits/stdc++.h> 

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int N = 1e5 + 7;

int v[N], d[N], w[N], val[N], weight[N], who[N], par[N];
ll dp[N];
vector<int> g[N], ord;

void dfs(int u) {
    for (auto v : g[u]) {
        par[v] = u;
        dfs(v);
    }
    ord.push_back(u);
}

void add(int u) {
    int x = u;
    while (x != 0) {
        if (x != u && val[x] >= val[u]) {
            dp[x] += dp[u];
        }
        x = par[x];
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    int n, m, k; cin >> n >> m >> k;
    for (int i = 2; i <= n; ++i) {
        int p; cin >> p;
        g[p].push_back(i);
    }
    for (int i = 1; i <= m; ++i) {
        cin >> v[i] >> d[i] >> w[i];
        val[v[i]] = d[i];
        weight[v[i]] = w[i];
    }
    dfs(1);
    
    for (auto u : ord) {
        dp[u] += weight[u];
        
        ll s = 0;
        for (auto v : g[u]) s += dp[v];
        ckmax(dp[u], s);
        add(u);
    }
    cout << dp[1] << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...