How to quickly find the vertex that has the most edges and is not connected to the given vertex?

Question

Algorithms

The whole essence of the question is described in the title, I will add that the graph is given by a list of edges. How to do this quickly, not by brute force. (in some cases, the graph can be a tree, this will help somehow), the task itself:
https://acmp.ru/asp/do/index.asp?main=task&id_cour...

Answer 1

In general, no way. There is no other way than to view all the vertices that are not related to this one.
But usually you don't have to solve this problem once for a particular vertex. As in the above problem - you need to solve it for all the vertices of the graph at the same time. Moreover, in the above problem, the graph is always a tree.
You can, for example, calculate the dynamics - for each directed edge, return the maximum degree in the subtree, not counting the root of this subtree. If the edge leads to a leaf, then the answer is minus infinity - there are no vertices. Otherwise, we enumerate all the edges from the end of the edge (except the reverse one) and take the maximum from the DP for them and the degrees of the ends of the vertices. To find the maximum vertex for a given one, you only need to go through all the outgoing edges and find the maximum in the DP.
But this task can be easier: Find all vertices with the maximum degree. If out of 3 or more, then find 2 of them that are not related (take any, then any one more. If they are connected, then take any third - it is not related to one of the first two).
If there are 2 of them, then check if they are not connected. If they are adjacent or there is only one such, then find in the graph one more vertex with the maximum degree, which is not connected with at least one of these two. To make it work for a line - get an array and add 1 to all neighbors of each of the 1/2 maximum vertices. Then look at those where there is 0 (or 1, if there are two maximum).
Also consider as an answer a pair of neighbors for the maximum vertex, if there is one. This is to select the 2 largest numbers in the array - it is done per line.
Why does it work? It is clear that in the problem it is necessary to find a pair of unconnected vertices with the maximum sum of degrees. Obviously, in the case of three or more maxima or two unrelated maxima, this algorithm will give the most optimal answer - the 2 largest numbers in the array. It's better not to do it.
Now consider the case of two connected maximal vertices. Let's consider the optimal answer. If it does not have one of the maximum vertices, then we could replace one of the ends with a maximum. We can't do this unless both ends are connected to both maxima, which would mean cycles in the graph. But we have a tree! Hence, the optimal answer necessarily contains one of the maximal vertices. But we went over this option in the algorithm.
There remains the case of one maximal vertex. Again, the optimal answer does not contain it, only if it cannot be improved - which means that both ends are connected to the maximum vertex. But we have dealt with this case as well.

Answer 2

The task has a limit of 2*10^5, so this option is not suitable (the task itself: https://acmp.ru/asp/do/index.asp?main=task&id_cour... ), mb I'm somehow wrong understood the condition