AT_arc171_c [ARC171C] Swap on Tree题解

zpy12345 · 2026-11-12 16:44:43 · 题解

[ARC171C] Swap on Tree

安利一下我的博客！

这题真的有这么复杂吗？感觉我的做法很简单啊。

思路

设 dp_{i,j} 为考虑 i 的整个子树，其中 i 与儿子的边断了 j 条，可以得到的不同棋子序列的数量。特别的，如果一个棋子序列可以由多个操作序列得到，我们只考虑使得 i 与儿子的边断开数量最多的那个操作序列。由于 i 与儿子的边断了 j 条，意味着在整个操作过程中有 j+1 个不同的棋子曾经经过 i，我们可以在这些棋子经过的时候断掉 i 与父亲的连边，从而将这 j+1 个棋子中的某个棋子替换掉。

考虑类似于树形背包，在 i 原本的基础上增加了一个 i 的儿子 u，考虑转移。

若 i 与 u 的这条边断掉： dp_{i,j+1}=dp_{i,j}\times dp_{u,k}\times k \times j

若 i 与 u 的这条边不断：dp_{i,j}=dp_{i,j} \times dp_{u,k}

代码

时间复杂度 O(N^2)。

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,dp[3005][3005],si[3005];
vector<int> a[3005];
void dfs(int x,int fa)
{
    si[x]=1,dp[x][1]=1;
    for(int i=0;i<a[x].size();i++)
        if(a[x][i]!=fa)
        {
            dfs(a[x][i],x);
            for(int j=si[x];j>=1;j--)
            {
                int res=0;
                for(int k=1;k<=si[a[x][i]];k++)
                {
                    dp[x][j+1]=(dp[x][j+1]+1ll*dp[x][j]*dp[a[x][i]][k]%mod*j*k)%mod;
                    res=(res+1ll*dp[x][j]*dp[a[x][i]][k]%mod)%mod;
                }
                dp[x][j]=res;
            }
            si[x]+=si[a[x][i]];
        }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        a[u].push_back(v),a[v].push_back(u);
    }
    dfs(1,0);
    int ans=0;
    for(int i=1;i<=n;i++) ans=(ans+dp[1][i])%mod;
    cout<<ans;
    return 0;
}