题解：AT_arc171_c [ARC171C] Swap on Tree

Qiuliyang · 2026-11-11 15:21:37 · 题解

题解：AT_arc171_c [ARC171C] Swap on Tree

我说这比 Rolling Hash 简单吧。这怎么有紫。

给出一个时间复杂度可以做到 \mathcal{O}(n \log n)，空间复杂度 \mathcal{O}(n) 的做法。

思路

很明显的 DP。

我们考察一些性质。

1. 对于一个子树，其最多与外面互换一个元素。
2. 每个节点上的颜色都是不同的，所以不管从外面互换的是那个颜色，都是本质相同的。

于是我们直接设 dp_{u,0/1} 表示对于 u 子树，其会不会与外面交换，有多少种方案。

考虑转移，我们可以把一次转移刻画为若干次有设计 u 的交换。

先对于 dp_{u,0} 转移，就是不考虑外部的点。

枚举有哪些子节点会与其进行交换就贡献 dp_{v,1} 否则贡献 dp_{v,0}，注意还有顺序之分，所以要乘上一个阶乘。

我们又发现 dp_{u,1} 的转移其实可以看做是在做 dp_{u,0} 的转移中突然插入了一个和其父节点的交换。

于是对于一个固定的时间点钦定其和父节点的交换的方案数就与不和父节点交换的方案数形成双射。于是多乘上一个参与交换的子节点的个数加一即可，因为总共有这么多个交换时间点。

然后我们就可以写出转移式了，使用类似于背包或者是生成函数的东西来表示会很方便。

然后如果使用 NTT 科技可以做到 \mathcal{O}(n \log n)。朴素的卷积则是 \mathcal{O}(n^2) 的。

AC code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int n,dp[3005][2],f[3005],F[3005],fac[3005];
vector<int> g[3005];
int ksm(int a,int b)
{
    int ans = 1;
    while(b)
    {
        if(b % 2) ans = ans * a % mod;
        a = a * a % mod;
        b /= 2;
    }
    return ans;
}
void dfs(int u,int fa)
{
    if((fa && g[u].size() == 1) || !g[u].size())
    {
        dp[u][0] = dp[u][1] = 1;
        return;
    }
    int cnt = 0,mul = 1;
    for(int v : g[u])
    {
        if(v == fa) continue;
        dfs(v,u);
    }
    for(int v : g[u])
    {
        if(v == fa) continue;
        mul = mul * dp[v][0] % mod;
//      if(u == 1) cout << "JUDGE:" << dp[v][1] << " " << dp[v][0] << endl; 
        f[++cnt] = dp[v][1] * ksm(dp[v][0],mod-2) % mod;
    }
//  cout << "array f:\n";
//  for(int i = 1; i <= cnt; i++) cout << f[i] << " ";
//  cout << endl;
    for(int i = 1; i <= cnt; i++) F[i] = 0;
    F[0] = 1;
    for(int i = 1; i <= cnt; i++)
    {
        for(int j = cnt; j >= 1; j--)
        {
            F[j] += F[j-1] * f[i] % mod;
            F[j] %= mod;
        }
    }
//  cout << "array F:\n";
//  for(int i = 1; i <= cnt; i++) cout << F[i] << " ";
//  cout << endl;
    for(int i = 0; i <= cnt; i++)
    {
        dp[u][0] += mul * F[i] % mod * fac[i] % mod;
        dp[u][1] += mul * F[i] % mod * fac[i] % mod * (i+1) % mod;
        dp[u][0] %= mod;
        dp[u][1] %= mod;
    }
}
signed main()
{
    cin >> n;
    fac[0] = 1;
    for(int i = 1; i <= n; i++) fac[i] = fac[i-1] * i % mod;
    for(int i = 1; i < n; i++)
    {
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
//  for(int i = 1; i <= n; i++) cout << dp[i][0] << " " << dp[i][1] << endl;
    cout << dp[1][0] << endl;
    return 0;
}