#include <bits/stdc++.h> #include <friend.h> using namespace std; // subtask 4 int dp(int x, int t, bool used, vector<int> adj[], int confidence[], int memo[][2]) { if (memo[x][used]!=-1) return memo[x][used]; int sum=used*confidence[x]; for (auto y : adj[x]) { if (y==t) continue; if (used) sum=sum+dp(y, x, false, adj, confidence, memo); else sum=sum+max(dp(y, x, true, adj, confidence, memo), dp(y, x, false, adj, confidence, memo)); } return memo[x][used]=sum; } int findSample(int n, int confidence[], int host[], int protocol[]) { vector<int> adj[n]; for (int i=1; i<n; i++) { adj[host[i]].push_back(i); adj[i].push_back(host[i]); } int memo[n][2]; for (int i=0; i<n; i++) { memo[i][0]=-1; memo[i][1]=-1; } return max(dp(0, -1, true, adj, confidence, memo), dp(0, -1, false, adj, confidence, memo)); }