I am trying to solve this question:
There are n nodes in a tree numbered 1 to n. Each node has a value v. There are two players A and B. A and B take turns choosing nodes of the tree with A starting first. Each player can only choose a node which is directly connected to one of the node they have already chosen. A and B are assigned different nodes initially and then they start choosing nodes. The game continues until no player can choose a node. If any player is unable to choose a node, they skip their turn.
There are q queries where each query gives x and y which are the initial nodes assigned to A and B. For each query, what is the maximum value A and B can collect by choosing nodes as described above given both play optimally?
Given n,q < 10^5
This is what I have come with so far: For each query, consider only the shortest path between x and y. Both A and B are going to move towards each other on this path. Eventually they will meet in the middle on this path. Consider the edge between A and B. Then the maximum number of points A can collect is sum of all the nodes to the left of the edge and B can collect the sum of all the nodes to the right of the edge.
But this solution is O(q*n). Can this be solved in a more optimal way or is there any other approach for this?
Let's say that we have already rooted the tree at node z, and have already found the splitting edge between player A and B. Clearly the score for one of the players is exactly the sum of nodes on the subtree underneath that splitting edge, so that is easy to calculate.
Now our trouble is finding that splitting edge. Let's use a binary lifting LCA table to find the least common ancestor of A and B in log(n). From this we can get how long the path is. Once we have how long the path is we'll use our LCA table to walk half the path length up from the deeper node in log(n) as well.
LCA code can be found here: https://cp-algorithms.com/graph/lca_binary_lifting.html
Thank you for reply MSchallenkamp.
According to the LCA link above we will need to pre process the tree in O(n*lg n). This requires that we know the root of the tree. But in our case we first need to find out the root or the breaking edge which might be different for each query. Am I missing something here?
Also how can we calculate for all edges, the sum of all the nodes to the left of the edge and to the right in less than O(n^2) so that we don't have to calculate it again for each query?
It doesn't matter where we root the tree. We can choose that once and leave it the same for all the queries. Then we'll go through that rooted tree and calculate for each subtree what the total sum of that subtree is. If we do that bottom to top it will take total linear time. Then whenever we find a split edge we have a subtree on one side and a remainder on the other. I.e. we just read the subtree total for one part and subtract it from the overall total for the other.