思路

题意简述：给定一棵以 1 为根、共 $n$ 个结点的树。对每个结点 $x$ 定义：

• $sz_x$：以 $x$ 为根的子树大小（结点数）；
• $mx_x$：$x$ 的所有儿子中，子树大小的最大值；若 $x$ 是叶子，则 $mx_x=0$。

有 $q$ 次询问，每次给出 $x$，要求 $O(1)$ 地回答 $mx_x$。

做法是一次从根出发的树形 DFS（后序遍历）：

1. 进入结点时，初始化 $sz_x=1$（只算自己），$mx_x=0$；
2. 对每个邻居 to，若它不是父亲，就递归处理 to；
3. 子结点处理完回到 $x$ 时，它的 $sz_{to}$ 已经算好，于是：
   • sz[x] += sz[to]，把儿子的子树并入自己的子树；
   • mx[x] = max(mx[x], sz[to])，更新儿子子树规模的最大值；
4. DFS 结束后，每个结点的 $mx$ 都已就绪，询问直接输出即可。

正确性：DFS 的后序性质保证处理完一个结点时，它所有儿子的子树大小都已经计算完毕；sz 的累加式正是子树大小的定义，mx 的取最大值正是“所有儿子子树规模的最大值”；叶子没有儿子，mx 保持初始值 0，符合定义。

复杂度：每个结点、每条边只被访问常数次，预处理 $O(n)$，每次询问 $O(1)$，总时间 $O(n+q)$；空间 $O(n)$，用于存树和递归栈（最坏情况下树退化成链，递归深度为 $n$）。

代码

#include<bits/stdc++.h>
#define int long long
#define dd double
#define str string
#define el cout << '\n'
#define re return
#define ff first
#define ss second
#define pll pair<int,int>
#define pdd pair<dd,dd>
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;

const int N = 1e5+10;
// 每个结点：mx 为儿子子树规模最大值，sz 为自身子树大小，son 存所有邻接点
struct node{
    int mx=0;
    int sz = 1;
    vector<int>son;
};
node a[N];
int n;

// 树形 DFS：cur 为当前结点，lst 为父结点（避免走回头路）
void dfs(int cur, int lst){

    for(int to: a[cur].son){
        if(to==lst)continue;

        // 先递归处理儿子，回溯时儿子的 sz/mx 已经算好
        dfs(to, cur);

        // 用儿子子树大小更新当前结点的最大势力值
        a[cur].mx = max(a[cur].mx, a[to].sz);
        // 把儿子的整棵子树并入当前子树
        a[cur].sz += a[to].sz;
    }

}

void go(){
    cin>>n;
    // 读入 n-1 条边，建成无向树
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        a[u].son.pb(v);
        a[v].son.pb(u);
    }

    // 从根结点 1 开始预处理，0 表示没有父亲
    dfs(1, 0);

    int q;cin>>q;
    // 每个询问 O(1) 输出预处理结果
    while (q--)
    {
        int x;cin>>x;
        cout<<a[x].mx<<endl;
    }

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int _=1;
    // 本题只有一组数据，故下面的循环只执行一次
    while(_--){
        go();
    }
    return 0;
}