#include "friend.h" #include <bits/stdc++.h> #define pb push_back using namespace std; int dp[1005][2]; int a[200005]; vector<int> edges[1005]; void dfs(int u, int p){ dp[u][1] = a[u]; for(auto v : edges[u]){ if(v == p)continue; dfs(v, u); dp[u][0] += dp[v][1]; dp[u][1] = max(dp[u][1], dp[v][0]); } dp[u][1] = max(dp[u][1], dp[u][0]); } int findSample(int n,int confidence[],int host[],int protocol[]){ int ans=0; for(int i=0;i<n;i++)a[i] = confidence[i]; if(n <= 15){ int mask = 0; vector<int> friends[13]; for(int i=1;i<n;i++){ if(protocol[i] == 0){ friends[i].pb(host[i]); friends[host[i]].pb(i); }else { for(auto x : friends[host[i]]){ friends[i].pb(x); friends[x].pb(i); } if(protocol[i] == 2){ friends[i].pb(host[i]); friends[host[i]].pb(i); } } } mask = 1; while(mask < (1<<n)){ int cost = 0; vector<bool> used(n); for(int i=0;i<n;i++){ if(!((1<<i)&mask))continue; bool ok = true; for(auto x : friends[i])if(used[x])ok=false; if(ok)cost += confidence[i], used[i] = true; } ans = max(cost, ans); mask++; } }else if(protocol[1] == 1){ for(int i=0;i<n;i++)ans += confidence[i]; }else if(protocol[1] == 2){ for(int i=0;i<n;i++)ans = max(ans, confidence[i]); }else { for(int i=1;i<n;i++){ edges[i].pb(host[i]); edges[host[i]].pb(i); } dfs(0, 0); ans = max(dp[0][0], dp[0][1]); } return ans; }