Problem Link - Conquest
Problem Statement
Chef has been promoted to the rank of General in the Siruseri Armed Forces!
As part of his work, he is to lead q military expeditions into the neighbouring Republic of Tutaria.
Tutaria has n cities. The cities are numbered from 1 to n. These cities are connected by n-1 bidirectional roads, in a way that it is possible to travel from any city to any other city.
In the $i$th expedition, Chef travels from city a_i to city b_i in Tutaria. To do this, he will take a route, such that he never visits any city more than one time. More formally, Chef’s expedition can be represented as a sequence s of m distinct cities, where s_1 = a_i, s_m = b_i, and there is a road between s_j and s_{j+1} for all 1 \leq j < m.
Each city in Tutaria also has gold to loot. During an expedition, for each city Chef visits, he can choose whether he would or would not like to loot the city. Looting city i will give Chef v_i gold ingots. However, since he wants to avoid causing too much discontentment, he will not loot two adjacent cities during the same expedition. Notice that all expeditions are independent of each other - his choice of cities to loot during one expedition does not affect his options in subsequent expeditions.
Subject to these requirements, find the highest total gold that Chef can receive on each trip.
Approach
To solve the problem, the logic is based on finding the path between the two cities Chef visits and ensuring that the maximum gold can be looted along this path without looting two adjacent cities. The tree structure (with n-1 roads) allows us to use techniques like Depth First Search (DFS) and Lowest Common Ancestor (LCA) to efficiently find and handle paths. We preprocess the tree with DFS to compute ancestors and depths, which helps in quickly calculating the LCA of any two cities.
Once the LCA is known, the problem reduces to splitting the path into two segments: from each city to the LCA. Dynamic programming is used along these paths to calculate the maximum loot Chef can gather, adhering to the rule that no two adjacent cities can be looted. The DP state keeps track of whether the current city is looted or skipped and propagates the maximum possible gold to the next step. After evaluating the two segments, the results are combined to get the optimal solution for that query.
Time complexity
The preprocessing takes O(n \log n), and each query runs in O(\log n) time.
Space complexity
The space complexity is O(n \log n) due to the storage of ancestors and dynamic programming states.