Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define ll long long
- using namespace std;
- const int N = 200005;
- int n;
- ll a[N];
- vector<ll> adj[N];
- ll dp[N];
- void DFS(int u, int parent) {
- dp[u] = a[u];
- for(int v : adj[u]) {
- if(v != parent) {
- DFS(v, u);
- dp[u] = max(dp[v] + a[u], dp[u]);
- }
- }
- }
- int main() {
- //freopen("in.txt", "r", stdin);
- //freopen("Summax1.inp", "r", stdin);
- //freopen("Summax1.out","w",stdout);
- ios_base::sync_with_stdio(false);
- cin.tie(0), cout.tie(0);
- cin >> n;
- for(int i = 1; i <= n; i++)
- cin >> a[i];
- for(int i = 1; i <= n; i++) {
- int u; cin >> u;
- if(u == 0) continue;
- adj[u].push_back(i);
- adj[i].push_back(u);
- }
- DFS(1, 0);
- cout << dp[1] << '\n';
- return 0;
- }
- /*
- 14
- 3 2 1 10 1 3 9 1 5 3 4 5 9 8
- 0 1 1 1 2 2 3 4 4 4 5 5 7 7
- ->22
- */
Advertisement
Add Comment
Please, Sign In to add comment