HDU 4008 Parent and son

Problem Description

Give you a tree with N vertices and N‐ 1 edges, and then ask you Q queries on “which vertex is Y's son that has the smallest number and which vertex is Y’s descendants that has the smallest number if we choose X as the root of the entire tree?”

Input

The first line of input is an integer T (T<=10) means the case number. 

The first line of each test case contains N(2 ≤ N ≤ 100,000) and Q(1 ≤ Q ≤ 100,000). 

Each of the following N ‐ 1 lines of the test case contains two integers a(1 ≤ a ≤ N) and b(1 ≤ b ≤ N) indicating an edge between a and b. 

Each of the following Q lines of the test case contains two integers X(1 ≤ X ≤ N) and Y(1 ≤ Y ≤ N, Y ≠ X) indicating an query. 

Output

For each query, output the Y's son which has the smallest number and Y's descendant that has the smallest number if X is the root of the entire tree. If Y has no sons then output “no answers!”. There is an empty line after each case.

Sample Input

1

7 3

1 2

1 5

2 3

2 4

5 6

5 7

1 2

5 3

3 2

Sample Output

3 3

no answers!

1 1

给出一棵树，根节点是不确定的，每个节点有一个不同标号，标号在1到n之间。

然后问当x为根的时候y节点的儿子中的标号最小值和所有子孙节点中的最小值。

首先可以以节点1为根进行一次预处理，求出每个节点的儿子中的最

小值和次小值以及子孙节点中的最小值和次小值。同时记录一个dfs序列，可以

o（1）的判断两个节点是不是包含关系。

接下来分类讨论，读入x，y。

1.如果y不包含x的，那么直接输出y儿子中的最小值和子孙中的最小值即可（注意判断是否有儿子）。

2.如果y包含了x

（1）如果y不是节点1，那么找到x到y路径中最接近y的点z

若z是y儿子中的最小值，输出y儿子的次小值和1.

否则输出y儿子中的最小值和1；

（2）如果y是节点1，且y没有其他分支输出no answer！

#include<stdio.h>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 100005;
vector<int> t, tree[maxn];
int tot, T, N, Q, x, y, m[maxn][2], M[maxn][2], dfn[maxn][2], fa[maxn];

void begin()
{
  tot = 0;
  for (int i = 1; i <= N; i++)
  {
    tree[i].clear();
    fa[i] = 0;
    m[i][0] = m[i][1] = 0x7FFFFFFF;
    M[i][0] = M[i][1] = 0x7FFFFFFF;
    dfn[i][0] = dfn[i][1] = 0;
  }
}

void dfs(int x, int xx)
{
  fa[x] = xx; dfn[x][0] = ++tot;  t.clear();
  for (int i = 0; i < tree[x].size(); i++)
    if (tree[x][i] != xx) t.push_back(tree[x][i]);
  tree[x] = t;
  for (int i = 0; i < tree[x].size(); i++)
  {
    int y = tree[x][i];
    dfs(y, x);
    if (y < m[x][0]) m[x][1] = m[x][0], m[x][0] = y;
    else m[x][1] = min(m[x][1], y);
    y = min(y, M[y][0]);
    if (y < M[x][0]) M[x][1] = M[x][0], M[x][0] = y;
    else M[x][1] = min(M[x][1], y);
  }
  dfn[x][1] = ++tot;
}

int half(int x, int y)
{
  int q = 0, h = tree[y].size() - 1, mid;
  while (true)
  {
    mid = (q + h) >> 1;
    if (dfn[x][0] >= dfn[tree[y][mid]][0] && dfn[x][1] <= dfn[tree[y][mid]][1]) return tree[y][mid];
    if (dfn[x][0] < dfn[tree[y][mid]][0]) h = mid - 1; else  q = mid + 1;
  }
}

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d%d", &N, &Q);
    begin();
    for (int i = 1; i < N; i++)
    {
      scanf("%d%d", &x, &y);
      tree[x].push_back(y);
      tree[y].push_back(x);
    }
    dfs(1, 1);
    while (Q--)
    {
      scanf("%d%d", &x, &y);
      if (dfn[x][0]>dfn[y][0] && dfn[x][1] < dfn[y][1])
      {
        int z = half(x, y);
        if (y != 1)
        {
          if (z == m[y][0]) printf("%d 1\n", min(m[y][1], fa[y]));
          else printf("%d 1\n", min(m[y][0], fa[y]));
        }
        else
        {
          if (tree[y].size() == 1) printf("no answers!\n");
          else
          {
            if (z == m[y][0]) printf("%d ", m[y][1]);
            else printf("%d ", m[y][0]);
            if (min(z, M[z][0]) == M[y][0]) printf("%d\n", M[y][1]);
            else printf("%d\n", M[y][0]);
          }
        }
      }
      else 
      if (dfn[y][0] + 1 == dfn[y][1]) printf("no answers!\n");
      else printf("%d %d\n", m[y][0], M[y][0]);
    }
    printf("\n");
  }
}