위대한 GDP
시간 제한1초메모리 제한512 MB
각 정점에 GDP와 인구가 주어진 트리에서 루트를 포함하는 연결된 부분 트리 중 총 GDP를 총 인구로 나눈 값이 최대가 되는 것을 찾는다.
문제
사랑하는 조국 트리토피아에서는 어떤 두 도시 사이를 이동하는 방법이 정확히 하나뿐이다. 반면 증오스러운 사이클로스탄에서는 모든 두 도시 사이를 이동하는 방법이 정확히 두 가지다.
사이클로스탄 대표단이 트리토피아를 방문한다. 당신은 이 기회를 이용해 그들에게 트리 같은 사회의 장점을 받아들이도록 설득할 수 있다는 것을 깨닫는다. 당신의 친구 외위빈이 사이클로스탄 대표단의 여행 계획을 정한다. 대표단에게 최대한 깊은 인상을 주기 위해, 당신은 외위빈을 설득해 방문하는 도시들의 1인당 GDP가 최대가 되도록 나라의 여러 지역으로 대표단을 데려가게 한다. 여행은 나라 안의 여러 갈래에 있는 도시들을 방문하는 것을 포함할 수 있고, 도시를 방문하지 않고 그냥 지나갈 수는 없다.
트리토피아의 유일한 공항은 수도 트리토폴리스에 있고, 사이클로스탄 대표단은 이곳에 도착한다.
입력
입력의 첫째 줄에는 트리토피아의 도시 수 n (1 ≤ n ≤ 100 000)이 주어진다. 다음 줄에는 n개의 음이 아닌 정수 c1, c2, . . . cn (각 i ∈ {1, 2, . . . , n}에 대해 0 ≤ ci ≤ 1 000 000)이 주어지는데, 이는 각 도시의 GDP다. 다음 줄에는 n개의 양의 정수 k1, k2, . . . , kn (각 i ∈ {1, 2, . . . , n}에 대해 1 ≤ ki ≤ 1 000 000)이 주어지는데, 이는 트리토피아 각 도시의 인구다. 다음으로 n − 1개의 줄이 주어지고, j번째 줄에는 서로 다른 두 정수 uj와 vj (1 ≤ uj, vj ≤ n)가 주어지는데, 이는 도시 uj와 vj 사이에 도로가 있음을 나타낸다. 트리토폴리스는 1번 도시다.
출력
트리토폴리스를 포함하는 트리토피아의 연결된 영역이 가질 수 있는 1인당 GDP의 최댓값을 출력한다. 절대 오차 또는 상대 오차가 10-6 이내인 답은 정답으로 인정된다.