CF2217H Closer

At your networking event, there are $ n $ deals waiting to happen. Each deal needs exactly two people, and every person is waiting for exactly one deal. So there are $ 2n $ people in total, and each deal ID $ 1 \ldots n $ appears on exactly two people's badges. For corporate reasons, the organisers place each person on a unique vertex in a tree with $ 2n $ vertices. Vertex $ v $ hosts a person with badge $ a_v $ . Deal $ i $ is sealed if, when the event begins, the two people with badge $ i $ are on adjacent vertices. Each sealed deal contributes $ w_i $ to your earnings. Before the event starts, you are allowed one reshuffle: 1. Choose any (potentially empty) set of edges such that no two chosen edges share a vertex (i.e., the edges form a matching). 2. For every chosen edge $ (u, v) $ , swap the people at vertices $ u $ and $ v $ . After reshuffling, what is the maximum you can earn from this event?

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 10^5 $ ). The next line contains $ n $ integers $ w_1, w_2, \ldots, w_n $ ( $ 0 \leq w_i \leq 10^5 $ ), where $ w_i $ denotes the profit from deal $ i $ . The next line contains $ 2n $ integers $ a_1, a_2, \ldots, a_{2n} $ . It is guaranteed that each value $ 1, 2, \ldots, n $ appears exactly twice in $ a $ . The next $ 2n-1 $ lines each contain two integers $ u $ and $ v $ ( $ 1 \leq u, v, \leq 2n, u \neq v $ ) — denoting that an edge connects nodes $ u $ and $ v $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

For each test case, output a single integer — the maximum total earning after a reshuffle.

Test 1. Swap edges $ (1,2) $ and $ (3,4) $ (they don't share vertices). Then the two 1s become adjacent on edge $ (2,3) $ , earning $ w_1=10 $ , which beats keeping the existing 2—2 adjacency worth 3. Test 2. The tree is a star. Swapping $ (1,2) $ moves badge 1 to the center, making it adjacent to the other 1, earning $ w_1=8 $ . Test 3. Swap $ (1,2), (3,4), (5,6) $ to seal two deals at once: edge $ (2,3) $ becomes 1—1 (gain 4) and edge $ (4,5) $ becomes 3—3 (gain 7), total 11.