题解：P16905 [CCO 2026] Tree Traversals

· · 题解

第二条限制等价于按深度分层，层间顺序不变，只考虑层内顺序的贡献。对于同一层，记录 dis_i 表示第 i 层中的两个点的最远距离，L_i 为 i 层所有点的最近公共祖先，有 dis_i=2 \times (i-dep_{L_i})。设 mx=\max dis_i。

分类讨论。

注意到 L_{i+1} 一定是 L_{i} 的子孙节点。因此遍历 L_i 的所有儿子 v，考察 mxdep_v 与 i 的关系。找到 mxdep_v > i 的 v，在这颗子树下的点作为结尾点我是放心的，因为它们直接接触更深的 i+1 层（或者说不需要走到 L_i，走到 L_{i+1} 就够了）。

因此把层内点按 dfs 序排序，二分得出在 v 子树下的 i 层点个数 len，作为结尾点方案数，其他顺序随意，因此，其对于总方案的贡献为 len \times (cnt_i-1)!。

预处理上述贡献，O(1) 输出即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
int n , q;
int dep[500010] , fa[500010][21];
struct edge {int to , nxt;}e[1000010];
int head[500010] , tot;
void add(int u , int v)
{
    ++ tot;
    e[tot].to = v;
    e[tot].nxt = head[u];
    head[u] = tot;
}
int lca(int u , int v)
{
    if(dep[u] < dep[v]) swap(u , v);
    int d = dep[u] - dep[v];
    for(int i = 0 ; i <= 20 ; i ++)
    {
        if(d & 1) u = fa[u][i];
        d >>= 1;
    }
    if(u == v) return v;
    for(int i = 20 ; i >= 0 ; i --)
    {
        if(fa[u][i] == fa[v][i]) continue;
        u = fa[u][i] , v = fa[v][i];
    }
    return fa[u][0];
}
int cnt = 0 , dfn[500010];
int mxdep[500010] , sz[500010];
void dfs(int u , int pa)
{
    fa[u][0] = pa , mxdep[u] = dep[u] = dep[pa] + 1 , dfn[u] = ++ cnt , sz[u] = 1;
    for(int i = 1 ; i <= 20 ; i ++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for(int i = head[u] ; i != 0 ; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == pa) continue;
        dfs(v , u);
        mxdep[u] = max(mxdep[u] , mxdep[v]);
        sz[u] += sz[v];
    }
}
int Dis(int u , int v)
{
    int LCA = lca(u , v);
    return dep[u] + dep[v] - 2 * dep[LCA];
}
int dis[500010] , LCA[500010];
vector<int> vec[500010] , V[500010];
int fac[500010];
void solve()
{
    scanf("%lld%lld" , &n , &q);
    for(int i = 1 , u , v ; i < n ; i ++) scanf("%lld%lld" , &u , &v) , add(u , v) , add(v , u);
    dfs(1 , 0);
    for(int i = 1 ; i <= n ; i ++) vec[dep[i]].push_back(i) , V[dep[i]].push_back(dfn[i]);
    for(int i = 1 ; i <= n ; i ++) sort(V[i].begin() , V[i].end());
    int mx = 0;
    for(int i = 1 ; i <= n ; i ++)
    {
        if(vec[i].size() == 0) break;
        int L = vec[i][0];
        for(int _ = 1 ; _ < (int)vec[i].size() ; _ ++) L = lca(L , vec[i][_]);
        dis[i] = 2 * (i - dep[L]) , LCA[i] = L;
        mx = max(mx , dis[i]);
    }
    int ans = 1 , res = 1;
//  printf("mx:%lld\n" , mx);
    for(int i = 1 ; i <= n ; i ++)
    {
        if(vec[i].size() == 0) break;
        if(mx == dis[i] && vec[i + 1].size() != 0)
        {
            int p = LCA[i] , len = 0;
//          printf("i:%lld p:%lld\n" , i , p);
            for(int j = head[p] ; j != 0 ; j = e[j].nxt)
            {
                int v = e[j].to;
                if(v == fa[p][0]) continue;
                if(mxdep[v] <= i) continue;
//              printf("v:%lld mxdep[v]:%lld\n" , v , mxdep[v]);
                int pos1 = lower_bound(V[i].begin() , V[i].end() , dfn[v]) - V[i].begin();
                int pos2 = upper_bound(V[i].begin() , V[i].end() , dfn[v] + sz[v] - 1) - V[i].begin() - 1;
                assert(len == 0);
                len = pos2 - pos1 + 1;
            }
//          printf("len:%lld\n" , len);
            if(len == 0) len = vec[i].size();// , printf("qwq");
            ans *= len * fac[vec[i].size() - 1] % mod , ans %= mod;
        }
        else
        { 
            ans *= fac[vec[i].size()] , ans %= mod;
        }
        res *= fac[vec[i].size()] , res %= mod;
    }
//  printf("res:%lld\n" , res);
    while(q --)
    {
        int k; scanf("%lld" , &k);
        if(k > mx) printf("%lld " , res);
        if(k == mx) printf("%lld " , ans);
        if(k < mx) printf("0 ");
    }
    puts("");

    tot = cnt = 0;
    for(int i = 1 ; i <= n ; i ++) vec[i].clear() , V[i].clear() , head[i] = dep[i] = sz[i] = mxdep[i] = dfn[i] = LCA[i] = 0;
}
signed main()
{
    fac[0] = 1;
    for(int i = 1 ; i <= 500000 ; i ++) fac[i] = fac[i - 1] * i % mod;
    int T; scanf("%lld" , &T);
    while(T --) solve();
    return 0;
}

实现细节参考代码，比如对于最后一层的特判，可以手推样例来了解为啥要这么做。