First, for each query we only care about the frecuencies of the given nodes, and not the nodes themselves. Then let's call a frecuency "big" if it has more than $$$K$$$ elements, and "small" otherwise. We can do different things according to the type of frecuencies involved in each query.

We can solve all queries where at least one frecuency is "big" offline doing a bfs multisource for each of the "big" frecuencies with a total complexity of $$$O(N^2/K)$$$. Then what remains is to solve queries where both frecuencies are "small".

So we can solve the problem in a total complexity of $$$O(N^2/K + QS)$$$, assuming we solve each of the remaining queries in $$$O(S)$$$.

Here is where it gets tricky, and there are different approaches with slightly different time complexities (using $$$Q=N$$$ below):

1. Brute force + LCA: $$$S = O(K^2logN)$$$, i.e. total complexity for optimal $$$K$$$ is $$$\sim O(N^{5/3}logN)$$$
2. Brute force + LCA improved: $$$S = O(K^2)$$$, i.e. total complexity for optimal $$$K$$$ is $$$O(N^{5/3})$$$ (this comes from computing LCA in $$$O(1)$$$)
3. Virtual tree: $$$S = O(KlogN)$$$, i.e. total complexity for optimal $$$K$$$ is $$$\sim O(N\sqrt{N}logN)$$$
4. Virtual tree improved: $$$S = O(KlogK)$$$, i.e. total complexity for optimal $$$K$$$ is $$$\sim O(N\sqrt{N}log(\sqrt{N}))$$$ (this comes from computing LCA in $$$O(1)$$$ when needed for the virtual tree)
5. Virtual tree extra improved: $$$S = O(K)$$$, i.e. total complexity for optimal $$$K$$$ is $$$O(N\sqrt{N})$$$ (this comes from computing LCA in $$$O(1)$$$ when needed for the virtual tree and getting rid of all sorts when computing a "small" query, which can be done with some precomputations and adjusting the virtual tree accordingly to avoid sorts).

In the official contest the time limit was quite tight as we aimed to cut 1 and 2 out (making it hard to get AC with 3 and 4 as well as a consequence). Here in codeforces the time limit is a bit more generous and it shold be a bit easier to get AC with most of the approaches.

I will answer queries in order from smallest rope length to biggest.

Call $$$A$$$ the goat going ccw and $$$B$$$ when it goes cw.

If $$$2\cdot l \leq$$$ perimeter it is easy to do the math with the angles because $$$A$$$ and $$$B$$$ won't intersect. (To do this you must precompute some information about the angles at each vertex and its distance from the first vertex, to then replace the rope length and get the result)

Note that you are only interested in the intersection of the curves $$$A$$$ and $$$B$$$, Also the curves are the concatenation of various arcs of circunferences made when the goat rotates around each vertex, reducing the radius each time you encounter a new vertex.

It is also clear that once the two curves intersect, you are no longer interested in the curve from that point, so you can eliminate the points of the polygon we are not interested in using as centers (subtracting the area of the triangle we are erasing).

You can do this with two pointers because if we can cover an arc of $$$B$$$ with $$$A$$$ at some moment, then with more rope length you will cover it too (to prove this you should see how the arcs are formed and the points between two arcs).

When you have the intersection it is the same as the case $$$2\cdot l \leq$$$ perimeter, with the current polygon and being careful of not counting that area twice (you can do this in $$$O(1)$$$ by calculating the triangle and reducing the last angles).