레이팅 미적용In the city of Shumen, Bulgaria, there is a large magic tree of \(n\) connected nodes,
where each node hides two magic values: red \(c_{i}\) and blue \(p_{i}\). Each value represents
the power that the node gives depending on its chosen color. Your goal is to
explore the harmonious paths in the tree.
Let’s consider the shortest path from the starting node \(A\) to the ending node \(B\)
in the tree. We traverse the nodes in order and choose either blue or red color for
the current node. After choosing the color of the current node, the state of the
path must be harmonious, i.e. no color may "mogg" another. We say that one color "moggs" another if we
have chosen it at least three more times than the other color. This rule must hold at every moment of
the path for the path to be considered harmonious.
We define the value of a path as the sum of the values of all nodes on that path, where each node’s value
is its magic value of the color it is colored with.
Your task is to determine the maximum value of \(q\) paths given with a starting and ending node if the
paths must be harmonic.
According to the given definition, it can be shown that there is always at least 1 harmonic path between
any 2 nodes in the tree.
The first line contains the natural numbers \(n\) and \(q\) (\(1 \le n\), \(q \le 10^{5}\)), the number of nodes in the magic
tree and the number of queries
The second line contains the \(n\) natural numbers \(c_{i}\) (−\(10^{9} \le c_{i} \le 10^{9}\)), the red values of the nodes.
The third line contains the \(n\) natural numbers \(p_{i}\) (−\(10^{9} \le p_{i} \le 10^{9}\)), the blue values of the nodes.
In the next \(n - 1\) lines, there are two natural numbers \(u\) and \(v\) (\(1 \le u\), \(v \le n\), u̸ = \(v\)), there is an edge
between the cities \(u\) and \(v\). There will be a path between any two nodes in the tree.
In the next \(q\) lines, there are two natural numbers \(u\) and \(v\) (\(1 \le u\), \(v \le n\)), the labels of the starting and
ending nodes of the path.
For each query, print one number on a separate line - the highest value of the harmonic path between the
starting and ending nodes of the query.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 27점 | n, \(q \le 15\) |
2 | 41점 | n, \(q \le 1000\) |
3 | 19점 | \(q \le 10000\) |
4 | 23점 | No additional constraints. |
4 1
10 10 10 10
-10 0 -10 0
1 2
2 3
3 4
1 4305 3
-5 -4 0 -3 3
3 1 -5 0 0
3 2
1 4
3 5
1 2
2 5
1 4
5 34
3
3Clarification of the first example: If we color node 1 red, node 2 blue, and nodes 3 and 4 red,
we get a harmonic path with a value of 30. There is no harmonic path with a higher value because
we have to color at least one of the 4 nodes blue, and the blue values do not increase the sum in this example.