#include <bits/stdc++.h> #define ll long long #define sz(x) int(x.size()) #define forn(i, n) for (i = 0; i < n; i++) #define all(x) x.begin(), x.end() #define pb push_back #define mp make_pair #define fr first #define se second using namespace std; const int MAXN = 1e5 + 1; vector<ll> grafo[MAXN]; bool vis[MAXN]; ll conf[MAXN]; pair<ll,ll>dfs(ll nod) { vis[nod]=1; pair<ll,ll>ret={conf[nod],0}, act; for(auto k:grafo[nod]) { if(vis[k]) continue; act=dfs(k); ret.se+=max(act.fr,act.se); ret.fr+=act.se; } return ret; } ll id[MAXN]; int findSample(int n, int confidence[], int host[], int protocol[]) { int ans = 0, act = 0; ll i, j; for(i=0; i<n; i++) { conf[i]=confidence[i]; id[i]=i; } for (i = 1; i < n; i++) { if (protocol[i] == 0) { grafo[i].pb(id[host[i]]); grafo[id[host[i]]].pb(i); } else { conf[id[host[i]]]++; id[i]=id[host[i]]; } } for(i=0; i<n; i++) { if(vis[id[i]]==0) { pair<ll,ll>ret=dfs(id[i]); ans+=max(ret.fr,ret.se); } } return ans; }