Road Network Destruction

demonstration of "important" roads for the 3rd example

This problem is from the Facebook Hackercup 2021 event - my solution was not good enough so I decided to share it with others. It is not difficult (at least with small map) and allows more than one approach.

Attention: input size is somewhat large, about 1Mb (to be close to original) - which may cause glitches while loading or copy-pasting.

There are N villages on the island, connected by N-1 roads. Every village contains a factory of some kind (e.g. some are baking bread, others make tools etc). In case of earthquakes (accompanied by tsunamis and volcano erruptions) some roads could be destroyed.

Earthquakes happen often here, so citizens themselves generally don't have much trouble due to road network being broken (they travel on foot over forest and use boats to swim around the island). However roads may be crucial for some village factories which use mass-transportation of goods by trucks. E.g. village baking bread needs to stay connected with village grinding grain to flour. Also village making axe heads wants to remain in touch with village making axe handles.

President of the country gives you information on which villages are "tied" by common production and asks to calculate how many roads could be destroyed without disrupting any production cycle.

To clarify: every village takes part in making only one product. For example if two villages mentioned above are producing axes (one making heads and other crafting handles) - they do not take part in producing hammers (handles for hammers then are produced by some other village). Hence there could be no more than N goods manufactured on the island - and we for convenience will simply enumerate them with integers G(i) for 1 <= i <= N.

Input data:

1. Very first line contains number of testcases (or different islands), call it T.
2. Then island description follows, starting with number of villages N (less than 200000) on separate line.
3. Next N-1 lines follow every with 2 values A and B, meaning that villages with such numbers are connected (1 <= A,B <= N).
4. At last here goes array G(1) ... G(N) - for every village in order it is ID of production in which given village takes part. As this array could be long it may be wrapped over multiple lines (so that copy-pasting has less chance of breaking your editor). Just read in numbers till exactly N values are ready.
5. If there are more islands, repeat from step "2".

Answer:

Simply give T values - how many roads could be destroyed (maximum) on each island without disrupting any production process.

Example:

input:
3
2
1 2
2 1
2
2 1
2 2
6
3 2
2 1
6 5
3 4
5 3
1 1 2 2 2 6

answer:
1 0 2

Here on the 1-st island we have 2 villages, each involved in different products, so the only road between them could be destroyed. The 2-nd island has 2 villages also, but working on the single product - so the road between them could not be broken. The last case is shown in the picture above - Villages 1-2 are making some project and villages 3-4-5 some other (with third product created by village 6 alone). So the roads shown in thin lines could be destroyed (one connection 2 and 3, other between 5 and 6).

Original Input Files

Problem in original contest has somewhat larger input - while you need not trying it, you are still encouraged to. Check whether your program becomes unbearably slow (in contest one has 6 minutes to upload answer) - or blows your machine's memory. Here comes the zip-archive - have fun!