Keen Tree Calculation
Contest: COMPFEST 15 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2500
Tags: binary search, data structures, dp, geometry, graphs, implementation, trees

There is a tree of $$$N$$$ vertices and $$$N-1$$$ edges. The $$$i$$$-th edge connects vertices $$$U_i$$$ and $$$V_i$$$ and has a length of $$$W_i$$$.

Chaneka, the owner of the tree, asks you $$$Q$$$ times. For the $$$j$$$-th question, the following is the question format:

- $$$X_j$$$ $$$K_j$$$ – If each edge that contains vertex $$$X_j$$$ has its length multiplied by $$$K_j$$$, 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.

Input format:
The first line contains a single integer $$$N$$$ ($$$2\leq N\leq10^5$$$) — the number of vertices in the tree.

The $$$i$$$-th of the next $$$N-1$$$ lines contains three integers $$$U_i$$$, $$$V_i$$$, and $$$W_i$$$ ($$$1 \leq U_i,V_i \leq N$$$; $$$1\leq W_i\leq10^9$$$) — an edge that connects vertices $$$U_i$$$ and $$$V_i$$$ with a length of $$$W_i$$$. The edges form a tree.

The $$$(N+1)$$$-th line contains a single integer $$$Q$$$ ($$$1\leq Q\leq10^5$$$) — the number of questions.

The $$$j$$$-th of the next $$$Q$$$ lines contains two integers $$$X_j$$$ and $$$K_j$$$ as described ($$$1 \leq X_j \leq N$$$; $$$1 \leq K_j \leq 10^9$$$).

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
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$$$.

Example input:
7
5 1 2
1 4 2
3 4 1
2 5 3
6 1 6
4 7 2
2
4 3
3 2

Example output:
18
11

Example input:
3
1 2 1000000000
2 3 1000000000
1
2 1000000000

Example output:
2000000000000000000

Editorial:
First, calculate the diameter of the initial tree.
For a question involving some vertex $$$p$$$. There are only two cases to consider:
• The diameter is the same as the diameter of the initial tree.
• The diameter goes through vertex $$$p$$$.
If the diameter goes through vertex $$$p$$$, then the diameter consists of two paths, each of them is from vertex $$$p$$$ to some other vertex, but the vertex immediately next to vertex $$$p$$$ in the two paths must be different.
Consider a vertex $$$p$$$. Let $$$q_1,q_2,q_3,\ldots,q_{\text{deg}[p]}$$$ be the vertices adjacent to $$$p$$$ with $$$\text{deg}[p]$$$ being the degree of $$$p$$$. For each $$$q_i$$$, calculate:
• $$$m_i$$$: The length of the edge connecting vertices $$$p$$$ and $$$q_i$$$.
• $$$c_i$$$: The maximum length of a path from $$$q_i$$$ to another vertex that does not pass through $$$p$$$.
All values of $$$c_i$$$ can be calculated using dynamic programming on tree with rerooting.
Notice that for a query involving vertex $$$p$$$ with a multiplier of $$$x$$$. The diameter that goes through vertex $$$p$$$ is the sum of the two biggest values of $$$m_i\times x+c_i$$$.
From this knowledge, we can consider each vertex $$$q_i$$$ as a line equation of $$$y=m_i\times x+c_i$$$. In order to be able to find the biggest value of $$$m_i\times x+c_i$$$ for any $$$x$$$, we maintain the maximum convex hull out of all those lines and we answer each query using binary search.
In order to be able to find the second biggest value of $$$m_i\times x+c_i$$$ for any $$$x$$$, we maintain several more convex hulls. Let $$$h_1,h_2,h_3,\ldots$$$ be the indices of the lines in the maximum convex hull sorted from the smallest $$$m$$$ to the biggest $$$m$$$. Then, for each $$$h_j$$$, we maintain a new maximum convex hull out of all lines $$$i$$$ with $$$m_{h_{j-1}}\leq m_i\leq m_{h_{j+1}}$$$ other than line $$$h_j$$$. We do that to maintain the candidate lines of the second biggest value if the biggest value is taken from line $$$h_j$$$. This can be done because lines $$$h_{j-1}$$$ and $$$h_{j+1}$$$ are two of the candidate lines, so the only other possible candidate lines that can produce bigger values in this particular location are lines $$$i$$$ with $$$m_{h_{j-1}}\leq m_i\leq m_{h_{j+1}}$$$.
Each line can only be in at most three different convex hulls, so the total number of lines to be considered in the making of all convex hulls for vertex $$$p$$$ is $$$O(\text{deg}[p]$$$). So in total, for all vertices $$$p$$$, the total number of lines is $$$O(N)$$$.
Time complexity: $$$O((N+Q)\log N)$$$