Note that we can replace the average of the lengths of the paths with the sum of the lengths of the paths, as the question's answer will not change.

For the first subtask, we can run ~N~ DFSs for each question. From each node in the tree, we can run a Depth First Search (DFS) to find the sum of the lengths of the paths originating from that node.

Time Complexity: ~\mathcal O(QN^2)~

For the second subtask, there were multiple different ways to find the sum of the lengths of the paths. However, we needed to be able to answer each question in subquadratic time in order to pass. One way to find the answer is to perform centroid decomposition on the tree. Another way is to perform dynamic programming on the tree. We will describe the dynamic programming solution.

Let ~sz[u]~ represent the number of nodes in ~u~'s subtree, including ~u~. Let ~down[u]~ represent the sum of the path lengths from all of the nodes in ~u~'s subtree to ~u~. Thus, ~down[u] = sum(down[v] + sz[v])~, where ~v~ is a child of ~u~. Let ~up[u]~ represent the sum of the path lengths from all nodes not in ~u~'s subtree to ~u~. Thus, ~up[u] = up[par[u]] + down[par[u]] - (down[u] + sz[u]) + (N - sz[u])~, where ~par[u]~ is the parent of ~u~. It is left as an exercise for the reader to prove these.

The sum of the length of the paths to ~u~ is ~down[u] + up[u]~.

Time Complexity: ~\mathcal O(QN)~ or ~\mathcal O(QN \log N)~

For the last subtask, we needed to achieve sublinear time per question. Instead of calculating the sum of the lengths of the paths, we will now calculate how much the sum changed.

We will use the same definitions of ~sz[u]~, ~down[u]~, and ~up[u]~ as subtask 2. In addition, we will define ~dist(u, v)~ as the length of the path from ~u~ to ~v~. To calculate ~dist(u, v)~, we can use a sparse table and Lowest Common Ancestor (LCA). Note that there are several other ways to do this.

Notice that when nodes ~i~ and ~j~ are swapped, only the path lengths from a node in ~i~'s subtree to a node outside both node ~i~ and node ~j~'s subtree have changed length, and similarly with the nodes in ~j~'s subtree. This means that any paths whose endpoints are outside of both ~i~ and ~j~'s subtree have not changed length.

To calculate the change, we need to subtract the sum of the lengths of the paths from all nodes in ~i~'s subtree to all nodes outside of both subtrees. It turns out, this value is exactly ~(up[i] - dist(i, j) \times sz[j] - down[j]) \times sz[i]~. Note that we do not need to account for the path section from a descendant of ~i~ to ~i~, as it will be added later on after moving the subtree.

Then, we need to add the sum of the lengths of the paths after moving the subtree. It turns out, this value is exactly ~(up[j] - dist(i, j) \times sz[i] - down[i]) \times sz[i]~. Note that we do not need to account for the path section from a descendant of ~i~ to ~i~, for the same reason as above (but this time added).

We need to do the same thing for ~j~'s subtree, which should result in: $$\displaystyle -(up[i] - dist(i, j) \times sz[j] - down[j]) \times sz[i] + (up[j] - dist(i, j) \times sz[i] - down[i]) \times sz[i] - (up[j] - dist(i, j) \times sz[i] - down[i]) \times sz[j] + (up[i] - dist(i, j) \times sz[j] - down[j]) \times sz[j]$$

Cleaning up the expression gives us: $$\displaystyle (up[i] - dist(i, j) \times sz[j] - down[j]) \times (sz[j] - sz[i]) + (up[j] - dist(i, j) \times sz[i] - down[i]) \times (sz[i] - sz[j])$$

Time Complexity: ~\mathcal O((N + Q) \log N)~