思路：我们定义一个dfn[i]，Maxndfn[i]来确定节点i的访问次序，以及其子节点的最大访问次序。那么另一个节点是其子树的节点当且仅当dfn[j]>=dfn[i]&&dfn[j]<=Maxdfn[i];
这是就可以先以1为根，dfs找出所有节点最小儿子，次小儿子，以及最小子孙，次小子孙。
剩下就可以分情况：
对于x,y:
1.若与y相连的边数为1，那么一定就是no answers!。
2.对于最小儿子节点的询问：
（1）若x是y的子节点，那么如果x包含在y的最小儿子子树中，那么就答案就是次小儿子与其父节点中较小的，否则就是最小儿子与其父节点中较小的。
（2）若y是x点子节点（设不是y的子节点的都是其根节点），那么就直接输出最小儿子。
3.对于最小子孙节点的询问：
（1）若x是y的子节点，那么如果x包含在y的最小子孙所在子树中（小于以y为根的子树），那么就答案就是次小子孙，否则就是最小子孙，其实这只设和y为1的情况，若y为其它节点，其最小子孙直接就是1。
（2）若y是x点子节点（设不是y的子节点的都是其根节点），那么就直接输出最小子孙。
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<queue> #define Maxn 100010 #define inf 0x7fffffff using namespace std; int son[Maxn],nson[Maxn],der[Maxn],nder[Maxn],n,q,dfn[Maxn],Maxdfn[Maxn],lab,dp[Maxn],road[Maxn],father[Maxn]; vector<int> head[Maxn]; void init() { int i; memset(son,0,sizeof(son)); memset(nson,0,sizeof(nson)); memset(der,0,sizeof(der)); memset(nder,0,sizeof(nder)); memset(dfn,0,sizeof(dfn)); memset(father,0,sizeof(father)); memset(dp,0,sizeof(dp)); memset(road,0,sizeof(road)); memset(Maxdfn,0,sizeof(Maxdfn)); lab=0; for(i=0;i<=n;i++) head[i].clear(); } void add(int u,int v) { head[u].push_back(v); head[v].push_back(u); } void dfs(int u,int f) { int i,v,si; dfn[u]=Maxdfn[u]=++lab; dp[u]=u; son[u]=nson[u]=der[u]=nder[u]=inf; si=head[u].size(); for(i=0;i<si;i++) { v=head[u][i]; if(v==f) continue; dfs(v,u); dp[u]=min(dp[u],dp[v]); Maxdfn[u]=max(Maxdfn[u],Maxdfn[v]); if(v<son[u]) { nson[u]=son[u]; son[u]=v; } else { if(v<nson[u]) nson[u]=v; } if(der[u]>dp[v]) { nder[u]=der[u]; der[u]=dp[v]; road[u]=v; } else if(nder[u]>dp[v]) nder[u]=dp[v]; } father[u]=f; } int main() { int i,j,a,b,t,x,y; scanf("%d",&t); while(t--) { init(); scanf("%d%d",&n,&q); for(i=1;i<n;i++) { scanf("%d%d",&a,&b); add(a,b); } dfs(1,1); for(i=1;i<=q;i++) { scanf("%d%d",&x,&y); int ans1,ans2; if(head[y].size()==1) { puts("no answers!"); continue; } if(dfn[x]<dfn[y]||dfn[x]>Maxdfn[y]) printf("%d %d ",son[y],der[y]); else { if(dfn[x]>=dfn[son[y]]&&dfn[x]<=Maxdfn[son[y]]) ans1=nson[y]; else ans1=son[y]; if(dfn[x]>=dfn[road[y]]&&dfn[x]<=Maxdfn[road[y]]) ans2=nder[y]; else ans2=der[y]; if(y!=1) ans1=min(ans1,father[y]),ans2=1; printf("%d %d ",ans1,ans2); } } printf(" "); } return 0; }