24917번 - 지역 순회 서브태스크점수

경기과학고등학교 출신 정치인들은 서로의 성공을 도모하기 위해 함께 모여 정당 경곽당을 창당했다. 이번 대선에 후보자 등록을 한 정후 역시 경곽당 소속이며, 전국을 순회하며 공약을 홍보할 것이다. 전국에는 1부터 N까지의 번호가 유일하게 매겨진 N 개의 지역이 있으며, 지역 사이를 서로 연결하는 N - 1 개의 길이 있다. 어떤 두 지역의 쌍도 길을 통해 오갈 수 있음을 보장한다.

전국에는 경곽 로컬 당지부, 경로당이 각 지역에 하나씩 분포하며 정후는 한 경로당에서 시작하여 시작한 곳과 다른 경로당에서 끝나도록, 그리고 하나의 길은 최대 한 번 방문하도록 지역을 순회할 예정이다. 또한, 이 과정에서 순회하는 지역 중 몇 개를 골라 공약을 홍보할 예정이다. i 번 도시에서 홍보한다면 a_i의 정치적 지지를 얻으며 t_i의 시간이 걸린다. a_i가 0보다 작거나 같을 수 있음에 주의하라. 다만, 지역 균형 발전을 위해 정후가 순회하는 지역의 순서상으로 연속한 M 개의 지역 중 적어도 하나의 지역에서는 홍보해야 한다. 지역 순회에 걸리는 총 시간은 정후가 홍보한 시간의 합이다. 시작한 곳과 끝난 곳에서는 반드시 홍보해야 한다.

정후의 측근 영우와 종경이는 정후의 순회 경로를 두고 팽팽한 신경전을 벌이고 있다. 영우는 정치적 지지의 합이 최대화되도록 순회해야 한다고 주장하며, 종경이는 정치적 지지의 합을 걸리는 총 시간으로 나눈 값이 최대화되도록 순회해야 한다고 주장한다. 이들을 위해 정치적 지지의 합의 최댓값과 정치적 지지의 합을 걸리는 총 시간으로 나눈 값의 최댓값을 각각 구하자. 두 경우에서 경로가 서로 다를 수 있음에 주의하라.

첫째 줄에 두 정수 N, M가 공백으로 구분되어 주어진다. 둘째 줄부터 N - 1 개의 줄에 걸쳐 두 정수 u_i, v_i가 공백으로 구분되어 주어진다. 트리에서 지역 u_i와 지역 v_i가 길로 연결되어 있음을 의미한다. N + 1째 줄부터 N 개의 줄에 걸쳐 i째 줄에 두 정수 a_i, t_i가 공백으로 구분되어 주어진다.

유일한 줄에 문제의 답을 공백으로 구분하여 두 실수로 출력한다. 정답과의 절대 오차 및 상대 오차는 10^-6까지를 허용한다. 이중 첫 번째 실수는 정치적 지지의 합의 최댓값이며, 두 번째 실수는 정치적 지지의 합을 걸리는 총 시간으로 나눈 값의 최댓값이다. 첫 번째 실수만을 모두 맞히거나 두 번째 실수만을 모두 맞히면 점수의 반을 받는다. 두 실수를 모두 출력해야 점수를 받을 수 있다.

• 2 ≤ N ≤ 100,000
• 1 ≤ M ≤ N
• 1 ≤ u_i < v_i ≤ N
• 1 ≤ t_i ≤ 10⁹
• -10⁹ ≤ a_i ≤ 10⁹
• 주어지는 모든 수는 정수이다.

• 2 ≤ N ≤ 200

• M = N

• M = 1

• u_i = i, v_i = i + 1

• 2 ≤ N ≤ 3,000

추가 제한 사항이 없다.