| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 101 | 51 | 30 | 69.767% |
정점이 $V$개인 트리가 주어진다. 각 정점은 $1$번 정점에서부터 $V$번 정점까지 번호가 붙어 있다. $i$번 정점에는 $1$에서 $9$까지의 숫자 중 하나인 $S_i$가 적혀 있다.
트리의 $a$번 정점과 $b$번 정점에 대해, $a$번 정점에서 $b$번 정점으로 가는 최단 경로에 포함된 각 정점에 적힌 숫자를 순서대로 이어 붙여 만든 10진법 정수를 $f(a, b)$로 정의하자.
예를 들어 $1$, $2$, $3$번 정점에 적힌 수가 각각 $3$, $4$, $1$이고, $1$번 정점에서 $2$번 정점으로 가는 최단 경로가 $1 \rightarrow 3 \rightarrow 2$라면, $f(1, 2) = 314$이다.
모든 가능한 정수 쌍 $(a, b)$ ($1 \le a, b \le V$)에 대해, $f(a, b)$를 모두 합한 값을 $1\,000\,000\,007$로 나눈 나머지를 구하라.
첫 번째 줄에 $V$가 주어진다. ($1 \le V \le 200\,000$)
두 번째 줄에 $S_1, \cdots, S_V$가 공백을 사이에 두고 주어진다. ($1 \le S_i \le 9$)
세 번째 줄부터 $V-1$개의 줄에 걸쳐 트리의 각 간선이 잇는 두 정점의 번호 $x$, $y$가 공백을 사이에 두고 주어진다. ($1 \le x, y \le V$)
입력으로 주어지는 모든 수는 정수이다.
첫 번째 줄에 답을 출력한다.
5 3 1 4 1 5 1 2 1 3 2 4 2 5
17560
주어진 트리는 다음과 같다. 큰 숫자는 정점에 적힌 숫자 $S_i$를, 작은 숫자는 정점의 번호 $i$를 나타낸다.
각 $(a, b)$에 대해 $f(a, b)$는 아래 표와 같다.
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | $3$ | $31$ | $34$ | $311$ | $315$ |
| 2 | $13$ | $1$ | $134$ | $11$ | $15$ |
| 3 | $43$ | $431$ | $4$ | $4\,311$ | $4\,315$ |
| 4 | $113$ | $11$ | $1\,134$ | $1$ | $115$ |
| 5 | $513$ | $51$ | $5\,134$ | $511$ | $5$ |
따라서, 표 안에 있는 값을 모두 더한 값을 $1\,000\,000\,007$로 나눈 나머지인 $17\,560$을 출력해야 한다.