#include "friend.h"
#include <algorithm>
#include <vector>
using namespace std;
// findSample funksiyasi n ta odam, ularning ishonch darajasi,
// mezbonlari va protokollarini qabul qiladi[cite: 43, 59].
int findSample(int n, int confidence[], int host[], int protocol[]) {
// Har bir kishi uchun ikkita holat:
// yes[i]: i-odam tanlansa, olinadigan maksimal qiymat
// no[i]: i-odam tanlanmasa, olinadigan maksimal qiymat
vector<int> yes(n), no(n);
for (int i = 0; i < n; i++) {
yes[i] = confidence[i];
no[i] = 0;
}
// Odamlar qo'shilish tartibining teskarisidan boshlab hisoblaymiz [cite: 9, 12]
for (int i = n - 1; i > 0; i--) {
int h = host[i];
int p = protocol[i];
if (p == 0) { // IAmYourFriend [cite: 13, 47]
// i tanlansa, h tanlanishi mumkin emas.
// i tanlanmasa, h xohlagan holatda bo'lishi mumkin.
yes[h] += no[i];
no[h] += max(yes[i], no[i]);
}
else if (p == 1) { // MyFriendsAreYourFriends [cite: 14, 47]
// i va h bir xil qo'shnilarga ega, lekin o'zaro do'st emas.
// Ikkalasidan biri yoki ikkalasi ham tanlanishi mumkin.
yes[h] = max({yes[h] + no[i], no[h] + yes[i], yes[h] + yes[i]});
no[h] += no[i];
}
else if (p == 2) { // WeAreYourFriends [cite: 16, 47]
// i va h o'zaro do'st va bir xil qo'shnilarga ega.
// Faqat bittasini tanlash mumkin.
yes[h] = max(yes[h] + no[i], no[h] + yes[i]);
no[h] += no[i];
}
}
// 0-odamda yig'ilgan yakuniy natijani qaytaramiz [cite: 49]
return max(yes[0], no[0]);
}
