Subtask 1

In subtask 1, ~N~ is at most ~10~. So just apply backtracking for every person – to choose or not to choose. The complexity is ~\mathcal O(N \times 2^N)~.

The sizes of ~N~ in other subtasks are too large to apply this solution, resulting in Time Limit Exceeded with this complexity.

Subtask 2

In subtask 2, all relations are MyFriendsAreYourFriends, forming a graph with no edge. That is equivalent to choosing all persons, with a complexity of ~\mathcal O(N)~.

Subtask 3

In subtask 3, all relations are WeAreYourFriends, forming a complete graph. Since every pair of two persons is connected by an edge, the answer to this problem is equivalent to choosing the maximum confidence among all people, with a complexity of ~\mathcal O(N)~.

Subtask 4

In subtask 4, all relations are IamYourFriend, forming a tree. So we apply the DP-in-tree method.

Define ~dp[i][j]~ as the maximum sum for the ~i^\text{th}~ node with status ~j~, where ~j = 0~ stands for not choosing this node and ~j = 1~ stands for choosing this node. Then:

1. If the ~i^\text{th}~ node is leaf, then

   • ~dp[i][j] = 0~, for ~j = 0~.
   • ~dp[i][j] = confidence[i]~, for ~j = 1~.

2. Otherwise,

   • ~dp[i][j] = \max(dp[k][0], dp[k][1])~, for ~j = 0~ and for all ~k~, where ~k~ is ~i~'s child.
   • ~dp[i][j] = dp[k][0]~, for ~j = 1~ and for all ~k~, where ~k~ is ~i~'s child.

The final answer is ~\max(dp[root][0], dp[root][1])~, where ~root~ stands for the root of this tree.

Subtask 5

Since there are only MyFriendsAreYourFriends and IamYourFriend relations, the resulting graph contains no odd cycle. That is, we obtain a bipartite graph. With all confidence equals to ~1~, the problem becomes finding maximum independent set in a bipartite graph. As we know, a set is independent if and only if its complement is a vertex cover. If the complement of independent set is not a vertex cover, then there exists at least one edge with end points ~u~ and ~v~, which is included in the independent set, conflicting with the definition of independent set. Trivially, a maximum independent set is the complement of minimum vertex cover.

According to Kőnig's theorem, in any bipartite graph, the number of edges in a maximum matching is equal to the number of vertices in a minimum vertex cover. Thus, we can apply the augmenting path algorithm to find out maximum cardinality matching in a bipartite graph, with complexity of ~\mathcal O(NE)~ or ~\mathcal O(\sqrt N E)~, depending on different implementations, where ~E~ is the number of edges.

Let ~k~ be the result of maximum cardinality bipartite matching, the answer to this problem equals ~N-k~, since maximum independent set is the complement of minimum vertex cover.

As for partitioning the graph into bipartite, we apply dfs to mark out the odd points and the even points, and then put all odd points on one side, even points on the other side.

In subtasks 2 and 4, the relations are MyFriendsAreYourFriends and IamYourFriend. However, the confidence values in those two subtasks are not all equal to ~1~. As a result, this solution can only solve subtask 5 correctly, and Wrong Answer for other subtasks.

Subtask 6

By using Greedy method to eliminate each person in the reverse order of building process, we will finally get the ~(p, q)~ pair for the last person. The answer will be ~\max(p, q)~ of the last person.

Here, we briefly introduce this method. Initially, we maintain two values ~p(x)~ and ~q(x)~ for each person ~x~, where ~p(x) = confidence[x]~ and ~q(x) = 0~. Physically, ~p~ stands for 'choose' and ~q~ stands for 'not choose'.

To simplify the notation, we call ~p~ for ~p(x)~, ~q~ for ~q(x)~, ~p'~ for ~p(y)~, ~q'~ for ~q(y)~.

1. WeAreYourFriends
   
   To eliminate ~y~, we can choose ~x~, or choose ~y~, or choose neither.

   1. Choose ~x~: ~p = p+q'~.
   2. Choose ~y~: ~p = p'+q~.
   3. Neither: ~q = q+q'~. So ~p = \max(p+q', p'+q)~, ~q = q+q'~.

2. MyFriendsAreYourFriends
   
   To eliminate ~y~, we can choose ~x~, or choose ~y~, or choose both, or choose neither.

   1. Choose ~x~: ~p = p+q'~.
   2. Choose ~y~: ~p = p'+q~.
   3. Choose both: ~p = p+p'~.
   4. Neither: ~q = q+q'~. So ~p = \max(p+q', p'+q, p+p')~, ~q = q+q'~.

3. IamYourFriend
   
   To eliminate ~y~, we can choose ~x~, or choose ~y~, or choose neither.

   1. Choose ~x~: ~p = p+q'~.
   2. Choose ~y~: ~q = p'+q~.
   3. Neither: ~q = q+q'~. So ~p = p+q'~, ~q = \max(p'+q, q+q')~.

The complexity of this scheme is ~\mathcal O(N)~. This method is capable of solving all subtasks.