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$