Revision en2, by NAACDI, 2022-08-11 20:37:54

Given a weighted undirected graph with N nodes and N-1 edges, we are also given S special nodes. For each special node, there is a convoy that is sent to the furthest node for each Si (if there are ties, the ending node is chosen at random). We are asked to find the maximum number of convoys that can't reach their target nodes if we remove one node from the graph and the number of ways to achieve this.

Example:

N = 4
0 1 3
1 2 10
1 3 11
S = 3
0 2 3
Ans: 3 1


We have 3 convoys({0 -> 3}, {2 -> 3}, {3 -> 2}), each of the convoys passes through node 1, so if we remove this node we have 3 convoys that can't get to their ending node, and the number of ways to do this is 1.

#### History

Revisions

Rev. Lang. By When Δ Comment
en2 NAACDI 2022-08-11 20:37:54 9
en1 NAACDI 2022-08-09 03:13:33 718 Initial revision (published)