CF1000G Two-Paths

You are given a weighted tree (undirected connected graph with no cycles, loops or multiple edges) with $ n $ vertices. The edge $ \{u_j, v_j\} $ has weight $ w_j $ . Also each vertex $ i $ has its own value $ a_i $ assigned to it. Let's call a path starting in vertex $ u $ and ending in vertex $ v $ , where each edge can appear no more than twice (regardless of direction), a 2-path. Vertices can appear in the 2-path multiple times (even start and end vertices). For some 2-path $ p $ profit $ \text{Pr}(p) = \sum\limits_{v \in \text{distinct vertices in } p}{a_v} - \sum\limits_{e \in \text{distinct edges in } p}{k_e \cdot w_e} $ , where $ k_e $ is the number of times edge $ e $ appears in $ p $ . That is, vertices are counted once, but edges are counted the number of times they appear in $ p $ . You are about to answer $ m $ queries. Each query is a pair of vertices $ (qu, qv) $ . For each query find 2-path $ p $ from $ qu $ to $ qv $ with maximal profit $ \text{Pr}(p) $ .

N/A

N/A

Explanation of queries: 1. $ (1, 1) $ — one of the optimal 2-paths is the following: $ 1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1 $ . $ \text{Pr}(p) = (a_1 + a_2 + a_3 + a_4 + a_5) - (2 \cdot w(1,2) + 2 \cdot w(2,3) + 2 \cdot w(2,4) + 2 \cdot w(4,5)) = 21 - 2 \cdot 12 = 9 $ . 2. $ (4, 4) $ : $ 4 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4 $ . $ \text{Pr}(p) = (a_1 + a_2 + a_3 + a_4) - 2 \cdot (w(1,2) + w(2,3) + w(2,4)) = 19 - 2 \cdot 10 = 9 $ . 3. $ (5, 6) $ : $ 5 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 4 \rightarrow 6 $ . 4. $ (6, 4) $ : $ 6 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4 $ . 5. $ (3, 4) $ : $ 3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 4 $ . 6. $ (3, 7) $ : $ 3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 7 $ .