크리스탈플라이

파이몬은 테이바트에 사는 특별한 나비인 크리스탈플라이를 나무 위에서 잡고 있다. 트리는 $n$개의 정점과 $(n - 1)$개의 무방향 간선으로 이루어진 연결 그래프이다.

Pixiv ID: 93964680

처음에 $i$번 정점에는 크리스탈플라이가 $a_i$마리 있다. 파이몬이 정점에 도착하면 그 정점에 남아 있는 크리스탈플라이를 모두 즉시 잡을 수 있다. 그런데 크리스탈플라이는 겁이 많다. 파이몬이 정점에 도착하면 인접한 정점들의 크리스탈플라이가 놀란다. $i$번 정점의 크리스탈플라이가 $t'$초의 시작 시점에 처음 놀라면, 그 크리스탈플라이는 $(t' + t_i)$초의 끝에 사라진다.

0초의 시작 시점에 파이몬은 1번 정점에 도착하고, 1초가 시작되기 전까지 그 자리에 머문다. 이후 매초 시작 시점마다 다음 두 가지 연산 중 하나를 고를 수 있다.

• 현재 정점에 인접한 정점 중 하나로 이동하고, 다음 초가 시작되기 전까지 그 정점에 머문다. (도착한 정점의 크리스탈플라이가 그 초의 끝에 사라지더라도 여전히 잡을 수 있다.)
• 현재 정점에 머물며, 다음 초가 시작되기 전까지 움직이지 않는다.

$10^{10^{10^{10^{10}}}}$초 동안 파이몬이 잡을 수 있는 크리스탈플라이의 최대 개수를 구하라.

입력에는 여러 개의 테스트 케이스가 있다. 첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 번째 줄에 정점의 개수 $n$ ($1 \le n \le 10^5$)이 주어진다.

두 번째 줄에 $n$개의 정수 $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le 10^9$)이 주어진다. $a_i$는 $i$번 정점에 있는 크리스탈플라이의 수이다.

세 번째 줄에 $n$개의 정수 $t_1, t_2, \cdots, t_n$ ($1 \le t_i \le 3$)이 주어진다. $t_i$는 $i$번 정점의 크리스탈플라이가 놀란 뒤 사라지기까지의 시간이다.

이어지는 $n - 1$개의 줄 중 $i$번째 줄에는 트리에서 정점 $u_i$와 $v_i$를 잇는 간선을 나타내는 두 정수 $u_i$, $v_i$ ($1 \le u_i, v_i \le n$)가 주어진다.

모든 테스트 케이스의 $n$ 합은 $10^6$을 넘지 않는다.

각 테스트 케이스마다 파이몬이 잡을 수 있는 크리스탈플라이의 최대 개수를 한 줄에 정수 하나로 출력한다.

첫 번째 테스트 케이스에서는 아래 전략을 따른다.

• 0초

  • 파이몬이 1번 정점에 도착한다.
  • 크리스탈플라이 1마리를 잡는다.
  • 2번과 3번 정점의 크리스탈플라이가 놀란다.

• 1초

  • 파이몬이 3번 정점에 도착한다.
  • 크리스탈플라이 100마리를 잡는다.

• 2초

  • 파이몬이 1번 정점에 도착한다.
  • 2번 정점의 크리스탈플라이가 사라진다.

• 3초

  • 파이몬이 2번 정점에 도착한다.
  • 4번과 5번 정점의 크리스탈플라이가 놀란다.

• 4초

  • 파이몬이 5번 정점에 도착한다.
  • 크리스탈플라이 10000마리를 잡는다.
  • 4번 정점의 크리스탈플라이가 사라진다.

두 번째 테스트 케이스의 최적 전략도 첫 번째 테스트 케이스와 같다. 다만 2번 정점의 크리스탈플라이는 2초의 끝이 아니라 3초의 끝에 사라지도록 예정되어 있어서, 파이몬이 그것을 잡을 수 있다.