魔王的领地管理

题目描述

在大陆的最深处，魔王统治着一片庞大而复杂的地下迷宫。

迷宫由 n 个房间构成，每个房间都可能通往若干下层房间，

整个迷宫呈一棵由房间 1 作为主殿开始向下延伸的巨大树状结构。

为了维持魔界秩序，魔王需要掌握每个房间旗下的势力情况。

🧿 房间的“势力值”定义

对于任意房间 $x$，它的直属下层房间（即它的儿子）各自掌控着一片区域，每片区域是一棵以该下层房间为根的子树。

魔王将房间 $x$ 的 最大势力值 定义为：

所有直属下层房间控制区中，房间数量最多的那一片区域的规模。 若房间 (x) 没有下层房间，则其最大势力值为 0。

魔王希望你帮他快速回答多个咨询——他会给出一些房间编号，想知道这些房间的最大势力值是多少。

正式的，给定一棵包含 n 个节点的有根树，根为节点 1。

对于每个节点 x，定义其 最大子树规模 $mx_x$ 为：

在所有以节点 x 的直接子节点为根的子树中，子树节点数量的最大值。 若节点 $x$ 没有子节点，则 $mx_x = 0$。

现给出这棵树的结构与若干询问。每次询问给出一个节点 x，你需要输出 $mx_x$ 。

输入格式

第一行一个整数 n：迷宫房间数量 $(1 \leq n \leq 10^5)$。

接下来 n - 1 行，每行两个整数 u, v，表示房间 u 的一条通往下层房间 v 的通道 $(1 \leq u,v \leq n)$。

接下来一行一个整数 q：魔王的咨询次数 $(1 \leq q \leq 10^5)$。

接下来 q 行，每行一个整数 x，表示魔王询问的房间 $(1 \leq x \leq n)$。

输出格式

每次询问输出一个整数，表示房间 x 的最大势力值。

样例 1

7
1 2
1 3
2 4
2 5
3 6
3 7
3
1
2
3

3
1
1

提示

        1
      /   \
     2     3
   /  \   /  \
  4    5 6    7

节点 1 的两个子树规模均为 3，因此 $mx_1 = 3$。 节点 2 的子树 4 和 5 均为 1，因此 $mx_2 = 1$。