A USACO Themed Problem by Eric Yang
Estimated Difficulty: USACO Gold / Codeforces 2100
Bessie is located in Farmer John's barn, which contains $N$ rooms $(2\leq N\leq10^{5})$, conveniently numbered $1...N$, and $M$ corridors $(N-1\leq M\leq2\cdot10^{5})$. These corridors connect pairs of rooms such that the barn is connected (each room is reachable from any other room). There can be multiple corridors connecting two rooms, and a corridor can connect a room to itself.
Each of these $M$ corridors has a digital display with an integer $x_{i}$ on it $(0\leq x_{i}\leq10^{9})$. Every time Bessie walks through a corridor, the corresponding $x_{i}$ is decremented by one.
Bessie wants to rennovate the barn by adding some corridors. She wants to perfect the barn's design, so she wants you to answer $Q$ queries $(1\leq Q\leq10^{5})$ concerning the barn.
For each query, you are given an integer $y$ $(0\leq y\leq10^{9})$. You want to figure out the minimum number of corridors Bessie has to build in order such that for all rooms $1...N$, Bessie can start at that room and set all $x_{i}$ to $y$ by walking through a series of corridors.
The first line contains $T$, the number of testcases.
In each testcase:
The first line contains three integers, $N$, $M$, and $Q$.
The next $M$ lines contain descriptions of the corridors. The descriptions are composed of three integers, $a$, $b$, and $x_{i}$ $(1\leq a,b\leq N)$. The corridor connects rooms $a$ and $b$, and the display inside starts with $x_{i}$.
The next $Q$ lines describe the queries. Each query has one integer, $y$, the value Bessie wants to set all $x_{i}$ to.
Print the answer for all $T$ testcases. For each testcase, print "TESTCASE" (without the quotes) on the first line. On the following lines, with one line per query, print the minimum number of corridors that have to be built in order for it to be possible that Bessie can make all $x_{i}$ equal to $y$ starting from any room.
15 7 21 2 32 3 22 4 13 1 43 4 25 2 34 5 5 0 3
TESTCASE12