給一顆結(jié)點(diǎn)數(shù)為(100,000)的樹，最多詢問100,000次。每次詢問對(duì)兩個(gè)結(jié)點(diǎn)X,Y，以X為根，Y的最小標(biāo)號(hào)的孩子，Y的最小標(biāo)號(hào)的后代。

吐槽：

    1. 這么難寫的題為什么大家都當(dāng)水題做阿...

算法分析：

    

    對(duì)于X,Y，我們求出其LCA，U。

    如果U是Y的父親，那么一切都不變。用預(yù)處理的結(jié)果就可以。

    如果U是Y，那么我們可以快速求出，含有后代X的Y的兒子X'。

    檢查X'是否是Y的最小孩子(兒子)。如果是，那么結(jié)果是Y的次小兒子(孩子)。否則是Y的最小兒子(孩子)。

    于是我們樹形DP，求出最小與次小(兒子，后代)就可以了。寫起來(lái)很猥瑣，容易出錯(cuò)。

    LCA的寫法是參照shi哥的代碼。

    先預(yù)處理求出u的(1,2,4,8,...)代祖先，

    先讓x,y處于同一層。

    然后讓x,y一點(diǎn)一點(diǎn)向上爬，直到爬到恰好x==y的位置就是LCA了。

    

#include<iostream>
#include<cassert>
#include<cstdio>
using namespace std;
const int maxb = 17;
const int V = 1<<maxb;
int e,P[V][maxb], head[V], nxt[V<<1], pnt[V<<1], mn[V], sd[V], mn1[V],sd1[V];
// dp
const int inf = ~0u>>2;
int dep[V];
void dfs(int u,int f){
    P[u][0] = f;
    for(int i =1; i< maxb; i++)
        P[u][i] = P[P[u][i-1]][i-1];
    if(f!=u) mn[u] = f; else mn[u] = inf;
    mn1[u] = sd1[u] = inf;
    sd[u] = inf;
    for(int i=head[u];i!=-1;i=nxt[i]) {
        int v = pnt[i];
        if(v == f) continue;
        dep[v] = dep[u] + 1;
        if(v < mn[u]) {sd[u] = mn[u]; mn[u] = v;}
        else if(v < sd[u]) sd[u] = v;
        dfs(v,u);
        int fst,snd;
        if(v > mn1[v]) {
            fst = mn1[v];
            snd = min(v, sd1[v]);
        }
        else {
            fst = v;
            snd = mn1[v];
        }
        if(fst < mn1[u]){
            sd1[u] = mn1[u];
            mn1[u] = fst;
        }
        else {
            sd1[u] = min(sd1[u],fst);
        }
    }
}
// build
void add(int u,int v){
    nxt[e] = head[u];
    head[u] = e;
    pnt[e++] = v;
}
// LCA
void go(int &u,int d){
    for(int i=0;i<maxb;i++){
        if((1<<i) & d) u = P[u][i];
    }
}
int LCA(int x,int y){
    if(dep[x] > dep[y]) swap(x,y);
    go(y,dep[y] - dep[x]);
    if(x == y) return x;
    for(int i=maxb-1;i>=0;i--){
        if(P[x][i] != P[y][i])
            x = P[x][i], y = P[y][i];
    }
    assert(P[x][0]==P[y][0]);
    return P[x][0];
}
// work
void work(int x,int y){
    int u = LCA(x,y);
    if(sd[y] == inf) {puts("no answers!"); return;}
    if(u!=y){
        printf("%d %d\n",P[y][0] == mn[y] ? sd[y] : mn[y], mn1[y]);
    }
    else {
        go(x,dep[x]-dep[y]-1);
        
        printf("%d %d\n",x == mn[y] ? sd[y]: mn[y] , y == 1 ? (min(mn1[x],x) == mn1[y]? sd1[y]: mn1[y]): 1);
    }
}
int main(){
    int test;
    scanf("%d",&test);
    while(test--){
        int u,v,n,m;
        e = 0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) head[i] = -1;
        for(int i=1;i<n;i++){
            scanf("%d%d",&u,&v);
            add(u,v);
            add(v,u);
        }
        dep[1] = 0;
        dfs(1,1);
        while(m--){
            scanf("%d%d",&u,&v);
            work(u,v);
        }
        puts("");
    }
}