25737번 - Two Paths 다국어

문제

You are given a tree $T$ consisting of $N$ vertices. Each edge has a positive integer weight. The weight of a path $P$ in $T$ is defined as the sum of weights of edges in $P,ドル denoted by $W(P)$.

You are given a total of $Q$ queries, each containing two vertices $u,ドル $v,ドル and two integers $A$ and $B$. For each query, you are to find two simple paths $P_1$ and $P_2$ in $T$ satisfying these requirements.

• $P_1$ and $P_2$ doesn’t share a vertex.
• $P_1$ starts from $u,ドル and $P_2$ starts from $v$.
• Among all $P_1$ and $P_2$ satisfying the conditions above, the value of $A\times W(P_1) +B\times W(P_2)$ should be maximized.

You should output the value of $A\times W(P_1) +B\times W(P_2)$ for each query.

입력

The first line contains two space-separated integers $N$ and $Q$.

Each of the following $N-1$ lines contains three space-separated integers $u,ドル $v,ドル $w$. This means that there is an edge in $T,ドル connecting vertices $u$ and $v$ with weight $w$.

Each of the following $Q$ lines contains four space-separated integers $u,ドル $v,ドル $A,ドル $B,ドル denoting a single query.

출력

For each query, output the maximum possible value of $A\times W(P_1) +B\times W(P_2)$. The answers should be separated by newlines.

제한

• 2ドル\le N\le 200,円 000$
• 1ドル\le Q\le 500,円 000$
• 1ドル\le u<v\le N$ for both edges and queries
• 1ドル\le w\le 10,円 000$
• 1ドル\le A,B\le 2\times 10^9$

힌트