Problem: gold_mine_ch1 (2021 quals)

**Note: This problem shares similarities with [Chapter 2](https://www.facebook.com/codingcompetitions/hacker-cup/2021/qualification-round/problems/C2). The solution to either chapter may help with solving the other, so please consider reading both first.**

Just like [logging](https://www.youtube.com/watch?v=7AheBqBk0iQ), mining is a key industry in Canada's primary sector. Prospectors use geological tools to find ore deposits, then [drill, and blast](https://www.youtube.com/watch?v=zPbY--IXGg8&t=463s) to excavate a system of underground tunnels for access to the ores.

Minerva is a contract miner who spends her days extracting gold ore from underground mines across Ontario. One particular gold mine she's contracting for consists of \(N\) underground caves, numbered from \(1\) to \(N\), with cave \(1\) having an exit to the surface. There are also \(N - 1\) tunnels running among the caves, the \(i\)th of which allows one to travel in either direction between caves \(A_i\) and \(B_i\). Each cave is reachable from cave \(1\) by a sequence of these tunnels.

Cave \(i\) is known to contain \(C_i\) ounces of gold ore. With her trusty dump truck, Minerva plans to drive underground starting in cave \(1\), collect as much gold ore as possible, and exit back to the surface through cave \(1\).

There's just one issue: the tunnels are highly unstable, and will cave in after Minerva drives through them. Therefore, she is only able to traverse each tunnel at most once. Fortunately, the caves themselves are reinforced with pillars and will never collapse — she may visit each cave any number of times (though she can only collect its gold ore at most once).

This safety measure may limit mobility. Thankfully, Minerva's truck is also equipped to be a drill rig. As she travels through the system of caves, she may at any point use it to travel from her current cave to *any* other cave by drilling a new tunnel. **In this chapter, the rig only has the energy to drill at most one such tunnel.** Unfortunately, this new tunnel will be just as unstable as the existing ones — Minerva will only dare travel through it once.

Please help Minerva determine the maximum weight of gold ore that can be collected if she begins in cave \(1\), spends any amount of time exploring the mine (traveling through tunnels, drilling at most one new tunnel, and collecting ore from any visited caves), and end up once again in cave \(1\).


# Constraints

\(1 \le T \le 35\)
\(1 \le N \le 50\)
\(0 \le C_i \le 20{,}000{,}000\)
\(1 \le A_i, B_i \le N\)

The sum of \(N\) across all mines is at most \(1{,}000\).


# Input

Input begins with an integer \(T\), the number of mines that Minerva is contracted to work. For each mine, there is first a line containing the single integer \(N\). Then, there is a second line containing \(N\) space-separated integers, \(C_{1..N}\). Then, \(N - 1\) lines follow, the \(i\)th of which contains the space-separated integers \(A_i\) and \(B_i\).


# Output

For the \(i\)th mine, output a line containing *"Case #i: "* followed by a single integer, the maximum weight of gold ore (in ounces) that Minerva can collect before leaving the mine.



# Sample Explanation

The first mine looks as follows:

{{PHOTO_ID:328916612261658}}

It's possible to visit both caves (collecting \(30\) ounces of ore) and then return to cave \(1\), for example by taking the tunnel from cave \(1\) to cave \(2\) and then drilling a tunnel back to cave \(1\).


The second mine looks as follows:

{{PHOTO_ID:271244381102893}}

It's possible to end up with the ore from all \(4\) caves, for example by taking the tunnel to cave \(3\), drilling to cave \(4\), and then taking tunnels to cave \(2\) followed by cave \(1\).


The third mine looks as follows:

{{PHOTO_ID:160428912890161}}

It's possible to end up with \(3\) ounces of ore, but Minerva cannot collect all \(4\) ounces while still returning to cave \(1\) and only drilling one tunnel.


Sample input:
5
2
10 20
1 2
4
1 1 1 1
2 1
4 2
1 3
4
1 1 1 1
2 1
4 1
1 3
6
5 4 1 3 2 4
5 1
5 4
5 3
5 2
6 3
9
2 14 7 6 11 3 6 1 8
4 5
6 7
8 9
1 3
6 8
2 4
4 1
1 8


Sample output:
Case #1: 30
Case #2: 4
Case #3: 3
Case #4: 12
Case #5: 32


Solution: The mine can be thought of as a rooted tree, with one node per cave, the root being node \(1\), and each tunnel corresponding to an edge.

Assuming \(N \gt 1\), Minerva's route will consist of driving along the path from node \(1\) to some other node \(a\), drilling a tunnel to some other node \(b\) (potentially with \(b = 1\)), and finally driving along the path from node \(b\) to node \(1\). Any given node pair \((a, b)\) is valid if and only if no undirected edge is traversed multiple times (in other words, the path from node \(1\) to node \(a\) shares no edges in common with the path from node \(b\) to node \(1\)). For such a path, the total weight of gold ore collected is equal to the sum of \(C\) values across all nodes which are part of at least one of the two paths.

We can observe that a choice of \((a, b)\) is valid if and only if either \(b = 1\), or \(a\) and \(b\) lie within the subtrees of different children of node \(1\). If they were to both lie within the subtree of the same child \(c\) of node \(1\), then both paths would include the undirected edge between nodes \(1\) and \(c\), which would be invalid.

We can also observe that the only node which will be part of both paths is node \(1\), and that the direction of each path is irrelevant (with both paths essentially being interchangeable). If we let \(F(i)\) be the sum of \(C\) values on the path between node \(1\) and node \(i\), then the total weight of gold ore collected will be \(F(a) + F(b) - C_1\).

Let \(G(i)\) be the maximum value of \(F(j)\) for any node \(j\) in node \(i\)'s subtree (including \(i\) itself). We can recursively compute the \(F\) and \(G\) values for all \(N\) nodes in \(O(N)\) time, based on the recurrences \(F(i) = F(P_i) + C_i\) (where \(P_i\) is node \(i\)'s parent) and \(G(i)\) equalling 
the maximum of \(F(i)\) and of \(G(c)\) (for each of node \(i\)'s children \(c\)).

Putting everything together, if node \(1\) has fewer than two children, the final answer will be \(G(1)\), while the answer will otherwise be \(G(c_1) + G(c_2) - C_1\), where \(c_1\) and \(c_2\) are the two distinct children of node \(1\) which yield the largest \(G\) values. It's also possible to arrive at a similar result without explicitly computing \(F\) and \(G\) separately.

[See David Harmeyer's solution video here](https://youtu.be/V1p4ZX-uDM8).


Code: #include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int LIM = 52;

int N, C[LIM];
vector<int> adj[LIM];

// Maximum path sum from i down to any leaf.
int rec(int i, int parent) {
  int m = 0;
  for (int j : adj[i]) {
    if (j != parent) {
      m = max(m, rec(j, i));
    }
  }
  return C[i] + m;
}

int solve() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> C[i];
    adj[i].clear();
  }
  for (int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  // Find up to 2 best children of root.
  int m1 = 0, m2 = 0;
  for (auto c : adj[0]) {
    int v = rec(c, 0);
    if (v > m1) {
      m2 = m1;
      m1 = v;
    } else {
      m2 = max(m2, v);
    }
  }
  return C[0] + m1 + m2;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}