#include <bits/stdc++.h> #define ll long long #define mp make_pair #define fi first #define se second #define pb push_back #define vi vector<int> #define pi pair<int, int> #define mod 1000000007 template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;} template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;} ll ksm(ll a, ll b) {if (b == 0) return 1; ll ns = ksm(a, b >> 1); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns;} using namespace std; const int maxn = 1050; int N, a[maxn]; vi g[maxn]; ll dp[maxn][2]; bool was[maxn]; bool sub2(int* a) { for (int i = 1; i < N; i++) if (a[i] != 1) return false; return true; } bool sub3(int* a) { for (int i = 1; i < N; i++) if (a[i] != 2) return false; return true; } bool sub4(int* a) { for (int i = 1; i < N; i++) if (a[i] != 0) return false; return true; } void dfs(int u, int p) { vector<ll> s(2); for (int v : g[u]) { if (v != p) { dfs(v, u); s[0] += max(dp[v][0], dp[v][1]); s[1] += dp[v][0]; } } dp[u][1] = a[u] + s[0]; dp[u][0] = s[1]; } ll findSample(int n, int* confidence, int* host, int* protocol) { N = n; if (sub2(protocol)) { ll sum = 0; for (int i = 0; i < n; i++) sum += confidence[i]; return sum; } if (sub3(protocol)) { int mx = 0; for (int i = 0; i < n; i++) chkmax(mx, confidence[i]); return mx; } if (sub4(protocol)) { for (int i = 1; i < n; i++) g[host[i]].pb(i); for (int i = 0; i < n; i++) a[i] = confidence[i]; ll res = 0; for (int i = 0; i < n; i++) { if (!was[i]) { dfs(i, i); res += max(dp[i][0], dp[i][1]); } } return res; } return 0LL; }