CF1866K.Keen Tree Calculation
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
There is a tree of N vertices and N−1 edges. The i -th edge connects vertices Ui and Vi and has a length of Wi .
Chaneka, the owner of the tree, asks you Q times. For the j -th question, the following is the question format:
- Xj Kj – If each edge that contains vertex Xj has its length multiplied by Kj , what is the diameter of the tree?
Notes:
- Each of Chaneka's question is independent, which means the changes in edge length do not influence the next questions.
- The diameter of a tree is the maximum possible distance between two different vertices in the tree.
输入格式
The first line contains a single integer N ( 2≤N≤105 ) — the number of vertices in the tree.
The i -th of the next N−1 lines contains three integers Ui , Vi , and Wi ( 1≤Ui,Vi≤N ; 1≤Wi≤109 ) — an edge that connects vertices Ui and Vi with a length of Wi . The edges form a tree.
The (N+1) -th line contains a single integer Q ( 1≤Q≤105 ) — the number of questions.
The j -th of the next Q lines contains two integers Xj and Kj as described ( 1≤Xj≤N ; 1≤Kj≤109 ).
输出格式
Output Q lines with an integer in each line. The integer in the j -th line represents the diameter of the tree on the j -th question.
输入输出样例
输入#1
7 5 1 2 1 4 2 3 4 1 2 5 3 6 1 6 4 7 2 2 4 3 3 2
输出#1
18 11
输入#2
3 1 2 1000000000 2 3 1000000000 1 2 1000000000
输出#2
2000000000000000000
说明/提示
In the first example, the following is the tree without any changes.
The following is the tree on the 1 -st question.
The maximum distance is between vertices 6 and 7 , which is 6+6+6=18 , so the diameter is 18 .
The following is the tree on the 2 -nd question.
The maximum distance is between vertices 2 and 6 , which is 3+2+6=11 , so the diameter is 11 .