# Parent and son

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?”

InputThe 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.
OutputFor 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
1 1
```
```#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<memory>
#include<bitset>
#include<string>
#include<functional>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

#define MAXN 100006
#define INF 0x3f3f3f3f

struct edge
{
int to, next;
}E[MAXN*2];
int tot, sz, head[MAXN], L[MAXN], R[MAXN], s[MAXN], fa[MAXN];
void init()
{
tot = 0;
sz = 0;
memset(s, 0, sizeof(s));
}
{
E[tot].to = t;
}
struct node
{
int min1, min2, id1, id2;
}sn[MAXN],st[MAXN];

void getmin(node& tmp, int num, int v)
{
if (tmp.min1 > num)
{
tmp.min2 = tmp.min1, tmp.id2 = tmp.id1;
tmp.min1 = num, tmp.id1 = v;
}
else if (tmp.min2 > num)
{
tmp.min2 = num, tmp.id2 = v;
}
}

void dfs(int u, int pre)
{
L[u] = ++sz;
sn[u].min1 = sn[u].min2 = st[u].min1 = st[u].min2 = INF;
for (int i = head[u]; i != -1; i = E[i].next)
{
int v = E[i].to;
if (v == pre) continue;
dfs(v, u);
fa[v] = u;
getmin(sn[u], v, v);
getmin(st[u], min(st[v].min1, v), v);
}
R[u] = sz;
}
int main()
{
int T, n, u, v, q, X, Y;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &q);
init();
for (int i = 0; i < n - 1; i++)
{
scanf("%d%d", &u, &v);
s[u]++;
s[v]++;
}
sz = 0;
fa[1] = INF;
dfs(1, 0);
while (q--)
{
scanf("%d%d", &X, &Y);
if (s[Y] == 1)
else if (L[X]<L[Y] || R[X]>R[Y])
printf("%d %d\n", sn[Y].min1, st[Y].min1);
else
{
int ans = 1;
if (Y == 1)
{
if (L[st[Y].id1] <= L[X] && R[st[Y].id1] >= R[X])
{
ans = st[Y].min2;
}
else
ans = st[Y].min1;
}
if (L[sn[Y].id1] <= L[X] && R[sn[Y].id1] >= R[X])
{
printf("%d %d\n", min(fa[Y], sn[Y].min2), ans);
}
else
printf("%d %d\n", min(fa[Y], sn[Y].min1), ans);
}
}
printf("\n");
}
}```

## HDU 4008 Parent and son （数据结构）

﻿﻿ 题意: 一颗结点数为(100,000)的树,最多询问100,000次.每次询问对两个结点X,Y,以X为根,Y的最小标号的孩子,Y的最小标号的后代. 思路:如果dfs n次那么时间复杂度无法承受,我们考虑只dfs一次. 以1为根节点dfs一次,记录每个点的最小和次小儿子值和最小后代值,考虑询问x, y,如果x不是y的子孙节点,那么答案就是y的最小儿子值和最小后代值. 如果x是y的子孙节点,又分为两种情况, 首先考虑y不为1的时候,那么y的最小后代值一定为1,如果x所在子树的y的儿子节点的值为

## 《深入理解Java虚拟机》：类加载的过程

<深入理解Java虚拟机>:类加载的过程 类从被加载到虚拟机内存中开始,到卸载出内存为止,它的整个生命周期包括:加载.验证.准备.解析.初始化.使用和卸载七个阶段.其中类加载的过程包括了加载.验证.准备.解析.初始化五个阶段. 下面详细讲述类加载过程中每个阶段所做的工作. 加载 加载时类加载过程的第一个阶段,在加载阶段,虚拟机需要完成以下三件事情: 1.通过一个类的全限定名来获取其定义的二进制字节流. 2.将这个字节流所代表的静态存储结构转化为方法区的运行时数据结构. 3.在Java堆中生成一