#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
/* Protocols: add new vertex i at step i, with following types:
1. type 0 = IAmYourFriend : edge between vertex i and host[i]
2. type 1 = MyFriendsAreYourFriends : edge between vertex i and
all friends of host[i], not includeing host[i]
3. type 2 = WeAreYourFriends : IAmYourFriend + MyFriendsAreYourFriends
Answer is the maximum cost independent set. There are 3 cases for each protocols:
1. alternate[v] = alternate[v] + confidence[i], confidence[v] = confidence[v] + alternate[i]
2. confidence[v] = confidence[v] + confidence[i], alternate[v] = alternate[v] + alternate[i]
3. confidence[v] = max(confidence[v], confidence[i]), alternate[v] = alternate[v] + alternate[i]
Proof 1:
Denote current graph as G. The solution for this graph is costG, before i is
added to the graph (and this is true for the next proofs). There are two
cases: either i is picked, or not. If i is picked, then v cannot be picked,
and vice versa. Thus we can solve this problem by keeping another array
alternate, denoting the cost if i is not picked.
Proof 2:
Denote current graph as G. The solution for this graph is costG, if v is not
picked, or costG + confidence, if v is picked. Thus it is exactly the same as
solving the graph G, with confidence[v] = confidence[v] + confidence[i].
Proof 3:
Denote current graph as G. Let the solution for this graph is costG. Then if
we pick v, the we cannot pick i. On the other hand, if we pick i, we cannot
pick v. If we pick either i or v, then their neighbours couldn't be picked.
So the optimal way is by max(i, v) or not picking it.Thus this is exactly the
same problem as finding costG with confidence[v] = max(confidence[v], confidence[i]).
For the transition, just alternate between the array alternate and confidence. The answer
is the maximum of alternate and confidence at vertex 0, after starting from the end of
protocols added.
*/
int findSample(int n, int confidence_[], int host[], int protocol[]) {
vector<int> confidence(n, 0), alternate(n, 0);
for (int i = 0; i < n; i++) confidence[i] = confidence_[i];
for (int i = n - 1; i > 0; i--) {
switch (protocol[i]) {
case 0: // IAmYourFriend
confidence[host[i]] = confidence[host[i]] + alternate[i];
alternate[host[i]] = alternate[host[i]] + confidence[i];
break;
case 1: // MyFriendsAreYourFriends
confidence[host[i]] = confidence[host[i]] + confidence[i];
alternate[host[i]] = alternate[host[i]] + alternate[i];
break;
case 2: // WeAreYourFriends
confidence[host[i]] = max(confidence[host[i]], confidence[i]);
alternate[host[i]] = alternate[host[i]] + alternate[i];
break;
}
confidence[host[i]] = max(confidence[host[i]], alternate[host[i]]);
}
return confidence[0];
}
