33873번 - 트리 뒤집기

문제

$N$개의 노드를 가진 루트가 1ドル$인 트리가 있다. 트리의 각 노드에 앞면과 뒷면에 모두 수가 쓰여있는 카드가 놓여있다.

송이는 이 트리에 다음과 같은 행동을 원하는 만큼 할 수 있다.

• 트리의 노드를 하나 선택한다.
• 선택한 노드를 루트로 하는 서브 트리의 카드들을 선택한 노드를 포함해 모두 뒤집는다.

송이는 카드의 앞면에 적힌 $N$개의 수의 합을 최대화하려고 한다.

이때 앞면에 적힌 $N$개의 수의 합의 최댓값과 뒤집는 행동을 최소 몇 번 해야 하는지 구해보자.

입력

첫째 줄에 노드의 개수 $N$이 주어진다. $(2 \leq N \leq 100,000円)$

둘째 줄에 노드 $i$에 놓인 카드의 앞면에 적힌 수 $F_i$가 공백으로 구분되어 주어진다. $(1 \leq i \leq N; -1,000円 \leq F_i \leq 1,000円)$

셋째 줄에 노드 $i$에 놓인 카드의 뒷면에 적힌 수 $B_i$가 공백으로 구분되어 주어진다. $(1 \leq i \leq N; -1,000円 \leq B_i \leq 1,000円)$

넷째 줄부터 $N - 1$줄에 걸쳐 트리 간선의 양 끝점 $u, v$가 공백으로 구분되어 주어진다. $(1 \leq u, v \leq N$; $u \ne v)$

입력으로 주어지는 수는 모두 정수이다.

출력

앞면의 합의 최댓값과 뒤집어야 하는 최소 횟수를 공백으로 구분하여 출력한다.

제한

힌트