链接：

题意很简单，给出一棵树，找出以x节点为根节点的情况下，y节点的最小儿子节点和最小子孙节点，每次进行一次搜索肯定是不行的，所以我们考虑只进行一次搜索，利用得到的结论去找到在其他情况下的解，先在以1为根节点的树中进行一遍深度优先搜索，记录下son[u][0](以u为根节点的子树中标号最小的子节点点)son[u][1](以u为根节点的树中标号次小的子节点)因为在选定不同的根节点导致图旋转的过程中，这两个节点最多有一个会变成u的父节点，所以直接确定另一个就可以了。low[u][0](以u为节点的子树中，标号最小的子孙节点)，low[u][1]（以u为根的所有的子树中所有low[v][0]的次小值，注意仔细理解这句话的意义，因为图旋转的过程中最多会有一棵子树在u节点的上方，所以同样可以确定另一个），具体的有一些细节的实现可以看代码

1 #include
      
         2 #include
       
          3 #include
        
           4 #define N 100005  5 #define inf 0x7fffffff  6 using namespace std;  7 int son[N][2],low[N][2];  8 int pre[N];  9 int head[N],cnt; 10 struct node 11 { 12     int v,next; 13 }; 14 node e[N*2]; 15 bool used[N]; 16 int min(int a,int b) 17 { 18     return a
         
          =0;i=e[i].next) 44     { 45         v=e[i].v; 46         if(used[v]) 47         continue; 48         if(v!=f) 49         dfs(v,u); 50         if(v
          
           son[u][1]) 53         swap(son[u][0],son[u][1]); 54         int minn=low[v][0]