#include <iostream> #include <vector> #include <algorithm> #include <set> typedef long long ll; using namespace std; const int maxn = 1e5 + 79; int dp[maxn][2]; // dp[vr][isiel nas kamos?] int dfs(int u, int fr, const vector<vector<pair<int, int> > >& g, int c[]) { if (dp[u][fr] != -1) return dp[u][fr]; int go = c[u], dont = 0; for (const pair<int, int>& i : g[u]) { int fr2 = (i.second ? fr : 0), p2 = (i.second != 1); go += dfs(i.first, (fr2 | p2), g, c); dont += dfs(i.first, fr2, g, c); } return dp[u][fr] = max(dont, go * (1 - fr)); } int findSample(int n, int c[], int h[], int pr[]) { vector<vector<pair<int, int> > > g(n); for (int i = 1; i < n; i++) g[h[i]].push_back({ i, pr[i] }); for (int i = 0; i < n; i++) for (int j = 0; j < 2; j++) dp[i][j] = -1; int ans = dfs(0, 0, g, c); //for (int i = 0; i < n; i++) for (int j = 0; j < 2; j++) cout << dp[i][j] << " \n"[j == 1]; return ans; }