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. Then assume that the original tree is rooted at the last node A chooses. Then the maximum number of points A can collect is sum of all the nodes in the left subtree + the root and B can collect the sum of all the nodes in the right subtree.

But this solution is O(q*n). Can this be solved in a more optimal way or is there any other approach for this?