Double X

AtCoder

IDarc213_c

Time4000ms

Memory256MB

Difficulty—

You are given two trees $T$ and $U$, each with $N$ vertices numbered from $1$ to $N$. The $i$\-th edge of $T$ connects vertices $u_i$ and $v_i$. The $i$\-th edge of $U$ connects vertices $b_i$ and $c_i$. You are also given a length-$N$ integer sequence $A=(A_1,A_2,\dots,A_N)$. For $k = 1, 2, \dots, N$, solve the following subproblem. > Does there exist a tuple of integers $(x_1, x_2, x_3, x_4)$ that satisfies the following conditions? If so, find the minimum value of $\sum_{i=1}^4 A_{x_i}$ for a tuple satisfying the conditions. > > * $x_1, x_2, x_3, x_4$ are all distinct. > * $x_1, x_2, x_3, x_4$ are all different from $k$. > * For all integers $(i,j)$ satisfying $1 \leq i \lt j \leq 4$, the $x_i x_j$ path in $T$ contains vertex $k$, and the $x_i x_j$ path in $U$ also contains vertex $k$. You are given $t$ test cases; solve the problem for each of them. ## Constraints * $1 \leq t \leq 10^5$ * $5 \leq N \leq 10^5$ * $1 \leq A_i \leq 10^9$ * $1 \leq u_i \lt v_i \leq N$ * $1 \leq b_i \lt c_i \leq N$ * $T$ and $U$ are trees. * The sum of $N$ over all test cases is at most $10^5$. * All input values are integers. ## Input The input is given from Standard Input in the following format. Here, $\mathrm{case}_i$ means the $i$\-th test case. $t$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_t$ For each test case, the input is given in the following format: $N$ $A_1$ $A_2$ $\dots$ $A_N$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_{N-1}$ $v_{N-1}$ $b_1$ $c_1$ $b_2$ $c_2$ $\vdots$ $b_{N-1}$ $c_{N-1}$ [samples]

Samples

Input #1

2
5
20 26 1 25 213
1 5
3 5
2 5
4 5
4 5
1 5
2 5
3 5
20
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288
1 2
2 3
1 4
1 5
2 6
3 7
3 8
3 9
2 10
1 11
8 12
6 13
5 14
11 15
13 16
1 17
7 18
9 19
15 20
1 2
2 3
2 4
4 5
2 6
1 7
6 8
3 9
3 10
7 11
7 12
1 13
3 14
3 15
8 16
1 17
3 18
2 19
1 20

Output #1

\-1 -1 -1 -1 72
70664 616 131968 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

For the first test case, when $k=1,2,3,4$, there does not exist $(x_1, x_2, x_3, x_4)$ satisfying the conditions. When $k=5$, $(x_1,x_2,x_3,x_4) = (1,2,3,4)$ satisfies the conditions.

API Response (JSON)

{
  "problem": {
    "name": "Double X",
    "description": {
      "content": "You are given two trees $T$ and $U$, each with $N$ vertices numbered from $1$ to $N$. The $i$\\-th edge of $T$ connects vertices $u_i$ and $v_i$. The $i$\\-th edge of $U$ connects vertices $b_i$ and $c_",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc213_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given two trees $T$ and $U$, each with $N$ vertices numbered from $1$ to $N$. The $i$\\-th edge of $T$ connects vertices $u_i$ and $v_i$. The $i$\\-th edge of $U$ connects vertices $b_i$ and $c_...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments