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?