8级T2的题解

xu_zhihao · 2025-06-28 22:17:14 · 个人记录

• 显然可以想到 O(n^2) 的树形 dp（枚举谁是根之后遍历树），显然需要优化。

• 根据经验，CCF 的出题数据一半都是随机的，树的层数应该不会太小，所以换根是枚举变化的路径不多，考虑记忆化路径，下次走到相同的路径直接返回，不用再递归了。

• 实测快的飞起。

第一版歪解

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int mod=1e9;
vector<int>e[N];
int dp[N];
int k[N]; 
unordered_map<int,int>mp[N];
void init(){
    k[0]=1;
    for(int i=1;i<N;i++){
        k[i]=k[i-1]*i;
        k[i]%=mod; 
    }
    return;
}
void dfs(int id,int fa){
    dp[id]=1;
    int cnt=0;
    //cout<<id<<endl;
    for(int to:e[id]){
        if(to==fa)continue;
        int f=mp[id][to];
        if(f){//直接调取 
            dp[id]*=f;
            dp[id]%=mod;
        }
        else{
            dfs(to,id);
            dp[id]*=dp[to];
            dp[id]%=mod;
            mp[id][to]=dp[to];//记忆路径 
        }
        cnt++;
    }
    //cout<<id<<endl;
    dp[id]*=k[cnt];
    dp[id]%=mod;
    return;
}
signed main(){
    init();
    int n;
    scanf("%lld",&n);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%lld%lld",&u,&v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        dfs(i,0);
        ans+=dp[i];
        ans%=mod; 
    }
    printf("%lld\n",ans);
} 

~虽然经我在考场测试得，1e5的菊花图就炸了。~

如果是菊花图就会退化成 O(n^2 \log n)。