| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 7 | 6 | 6 | 85.714% |
Albert는 2개의 트리 (tree) 를 이용한 놀이를 하고 있다. 첫 번째 트리는 $T_A$ 인데 $N_A$ 개의 노드를 갖고 있으며 ($a_1, a_2, \dots, a_{N_A}$ 로 나타낸다) 그 중 $S_A$ 에 속한 노드는 "특별한" 노드로 여겨진다. 마찬가지로 두 번째 트리는 $T_B$ 인데 $N_B$ 개의 노드를 갖고 있으며 ($b_1, b_2, \dots, b_{N_B}$ 로 나타낸다) 그 중 $S_B$ 에 속한 노드는 "특별한" 노드로 여겨진다. 아래 그림은 두 트리가 각각 3개의 노드를 가진 예제인데 (즉, $N_A = N_B = 3$), $S_A$ 에는 3개의 노드가 있고 $S_B$ 에는 1개의 노드가 있다. 특별한 노드는 그림에서 2중선으로 표시되어있다.
각 트리에서 노드를 하나씩 선택하여 간선으로 연결하면 하나의 트리로 합칠 수 있는데, 간선 $e = (a_i, b_j)$ 를 $T_A \cup T_B$ 에 추가한 트리를 $U_{i, j}$ 라 했을 때, $U_{i, j}$ 의 "완벽도" $S(i, j)$ 는 아래 규칙에 따라 정한다:
위 예제의 경우 $S(1, 1) = 1, S(1, 2) = 3, S(1, 3) = 1$ 임을 아래 그림을 통해 확인할 수 있다.
비슷한 방법으로 $S(2, 1) = 1, S(2, 2) = 3, S(2, 3) = 1, S(3, 1) = 1, S(3, 2) = 3, S(3, 3) = 1$ 임을 보일 수 있다.
임의의 $i, j$에 대하여 $S(i, j)$ 를 구하는 것은 너무 쉽기 때문에, Albert는 다음 값을 구해보기로 했다: $V(T_A, T_B) = \sum_{1 \le i \le N_A} \sum_{1 \le j \le N_B} S(i, j) \cdot (i + j)$. 위 예제의 경우 이 값은 60 이다.
입력으로 두 트리에 대한 정보가 주어졌을 때, $V(T_A, T_B)$ 값을 구해보자.
입력 첫 줄에 테스트 케이스의 수 $C$가 주어진다.
각 테스트 케이스의 첫 줄에는 $N_A$ 와 $M_A = |S_A|$ 가 공백으로 구분되어 주어진다. 둘째 줄에는 $M_A$ 개의 정수가 공백으로 구분되어 주어지는데, 이는 $S_A$ 에 속한 노드의 인덱스를 나타낸다. 다음 $N_A - 1$ 줄에 걸쳐 $T_A$ 의 간선이 주어지는데 각 줄에 간선 하나를 표현하는 두개의 정수가 공백으로 구분되어 주어진다. 이어서 두 번째 트리를 묘사하는 $N_B$ 와 $M_B = |S_B|$ 가 공백으로 구분되어 주어진다. 다음 줄에는 $M_B$ 개의 정수가 공백으로 구분되어 주어지는데, 이는 $S_B$ 에 속한 노드의 인덱스를 나타낸다. 다음 $N_B - 1$ 줄에 걸쳐 $T_B$ 의 간선이 주어지는데 각 줄에 간선 하나를 표현하는 두개의 정수가 공백으로 구분되어 주어진다.
각 테스트 케이스의 정답인 $V(T_A, T_B) = \sum_{1 \le i \le N_A} \sum_{1 \le j \le N_B} S(i, j) \cdot (i + j)$ 를 출력한다. 단, 이 값이 매우 클 수 있으므로 $10^9 + 7$ 로 나눈 나머지를 출력한다.
5 2 2 1 2 1 2 2 2 1 2 2 1 3 3 1 2 3 1 2 2 3 3 1 2 1 3 2 3 3 3 1 2 3 1 2 2 3 3 3 1 2 3 1 3 2 3 5 3 1 3 5 2 1 1 4 1 5 3 2 6 3 2 3 5 3 1 2 1 2 4 3 5 3 6 8 4 1 3 5 7 2 1 1 3 1 4 1 5 1 6 1 7 1 8 4 2 2 3 1 2 4 1 3 4
12 60 36 904 1600
예제 1: 모든 유효한 $i, j$에 대하여 $S(i, j) = 1$ 이다. 따라서 $\sum_{1 \le i \le N_A} \sum_{1 \le j \le N_B} S(i, j) \cdot (i + j) = \sum_{1 \le i \le 2} \sum_{1 \le j \le 2} (i+j) = 12$ 이다.
예제 2: 본문에서 다루었다.
예제 3: 모든 유효한 $i, j$에 대하여 $S(i, j) = 1$ 이다.
예제 4: 추가 설명 없음.
예제 5: $S(1, 1) = 10$, $S(2, 2) = 12$, $S(3, 3) = 3$, $S(4, 4) = 8$, $S(5, 1) = 2$, $S(6, 2) = 12$, $S(7, 3) = 3$, $S(8, 4) = 8$ 이다.