問題一覧 > 通常問題

No.2654 [Cherry 6th Tune] Re: start! (Black Sheep)

レベル : / AI推定難易度 : 2025 / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 26
作問者 : 👑 Kazun / テスター : 👑 AngrySadEight
お気に入りにしたユーザー ProblemId : 5662 / 自分の提出
問題文最終更新日: 2024-02-23 21:37:13
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 418 (Re: start!) (順位表) の他の問題:

Introduction

This problem revisits the theme of [Zelkova 8th Tune] Black Sheep, the very first problem written when the Zelkova contest, the predecessor of the current Cherry contest, was held.

Problem Statement

When reading this problem statement, pay attention to whether the indices of each "thing" are "0-indexed" or "1-indexed".

Black Sheep

In Black Sheep, the first term of an integer sequence is the $0$-th term.

Let $M \geq 2$. For an integer sequence $B=(B_0, B_1, \dots, B_M)$ of length $(M+1)$, if there exists an integer $j$ satisfying the following, this integer sequence $B$ is called a black sequence.

  • $0 \leq j \leq M$.
  • The $M$ integers $B_0, B_1, \dots, B_{j-1}, B_{j+1}, \dots, B_M$ are equal to one another, and that integer is different from $B_j$.

For example, $(1,1,2), (3,4,3,3,3)$ are black sequences, but $(5,6,7,7,7), (8,8,9,9,9), (0,0,0,0)$ are not black sequences.

For an integer sequence $C=(C_0,C_1, \dots, C_M)$ of length $(M+1)$, the goal is to make $C$ a black sequence by performing the following operation $0$ or more times.

  • Choose one of the following $2$ options and perform it.
    • Choose an integer $i$ between $0$ and $M$, inclusive, and add $1$ to the $i$-th term of $C$.
    • Choose an integer $i$ between $0$ and $M$, inclusive, and subtract $1$ from the $i$-th term of $C$.

What is the minimum number of operations required to make $C$ a black sequence?

You are given a simple undirected graph $T$ with $(N+1)$ vertices. This $T$ is a tree.

The $(N+1)$ vertices of $T$ are named vertices $0,1,2, \dots, N$. Among the $N$ edges of $T$, the $j~(1 \leq j \leq N)$-th edge connects vertex $u_j$ and vertex $v_j$.

For each of $x=1,2, \dots, N$, answer the following question.

  • Let $(p_0, p_1, \dots, p_d)$ (where $p_0=0, p_d=x$) be the simple path from vertex $0$ to vertex $x$. Is $d \geq 2$? Then, if $d \geq 2$, solve Black Sheep for $C=(A_{p_0}, A_{p_1}, \dots, A_{p_d})$.

Constraints

  • $1 \leq N \leq 2 \times 10^5$.
  • $0 \leq A_i \leq 10^9 \quad (0 \leq i \leq N)$.
  • $0 \leq u_j \leq N, 0 \leq v_j \leq N \quad (1 \leq j \leq N)$.
  • $T$ is a tree.
  • All input values are integers.

Input

The input is given from standard input in the following format.
$N$
$A_0$ $A_1$ $\cdots$ $A_N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_N$ $v_N$

Output

The output consists of $N$ lines.

On the $x~(1 \leq x \leq N)$-th line, letting $(p_0, p_1, \dots, p_d)$ be the simple path from vertex $0$ to vertex $x$, if $d \geq 2$, output the answer to Black Sheep for $C=(A_{p_0}, A_{p_1}, \dots, A_{p_d})$, and if $d \lt 2$, output -1.

Sample

Sample 1
Input
4
3 6 1 2 7
0 1
1 2
1 3
3 4
Output
-1
2
1
4

Here, we explain the cases $x=1, x=4$.

  • Case $x=1$: The simple path from vertex $0$ to vertex $1$ is $(0,1)$. Thus, $d=1$, and since $d \lt 2$, you must output -1.

  • Case $x=4$: The simple path from vertex $0$ to vertex $4$ is $(0,1,3,4)$. Thus, $d=3$, and since $d \geq 2$, you must solve Black Sheep.

    For Black Sheep on $C:=(A_0, A_1, A_3, A_4)=(3,6,2,7)$, $C$ can be made a black sequence with $4$ operations as follows.

    • Choose $i=0$ and add $1$ to the $0$-th term of $C$, changing it from $3$ to $4$.
    • Choose $i=0$ and add $1$ to the $0$-th term of $C$, changing it from $4$ to $5$.
    • Choose $i=0$ and add $1$ to the $0$-th term of $C$, changing it from $5$ to $6$.
    • Choose $i=3$ and subtract $1$ from the $3$-rd term of $C$, changing it from $7$ to $6$.

    This gives $C=(6,6,2,6)$, which is a black sequence. It can also be proved that it is impossible to make $C$ a black sequence with fewer than $4$ operations. Therefore, $4$ is the correct answer.

Sample 2
Input
7
4 46 464 4646 46464 464646 4646464 46464646
0 3
0 5
3 7
4 7
1 7
2 4
4 6
Output
4642
50642
-1
46460
-1
4688278
4642

Sample 3
Input
5
1 2 4 8 16 32
0 1
0 2
0 3
0 4
0 5
Output
-1
-1
-1
-1
-1

When the tree $T$ is a star centered at vertex $0$, for all of $x=1,2, \dots, N$, $(0, x)$ is the simple path from vertex $0$ to vertex $x$. That is, since $d=1$, you must output -1 on $N$ lines.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。