Codeforce 1172 B. Nauuo and Circle 解析(思維、DP)

今天我們來看看CF1172B
題目連結

題目
略，請直接看原題

前言

第一個該觀察的事情一直想不到，看了解答也想很久才知道為什麼對…

想法

這題的重點是要想到:一個節點$u$的所有子節點子樹必須佔據一整個連續的圓弧，否則如果有另外一個非子節點子樹在這些子節點子樹中間，那麼必定有另一個在$u$這棵子樹外的點連接過來，但是$u$最少必須連接被分開的兩個子節點區段，那麼一定會有交叉。
接下來就是自然的$dp$狀態:$dp[v]$代表$v$的子樹的可能性數量。
對於一個節點$v$，假設我們已經知道所有子節點的解答，假設有$k$個子節點，那麼有$k$個連續區段會排列在一個連續區段中，而$v$這個節點又可以隨便放在任意區段的間隔中。(注意，要算最後一個部份的間隔數，根節點可選的區段會形成一整個圓，而其他點都只有一個非完整的圓弧)
轉移式(假設不是根結點):$dp[v]=\prod\limits_{j\in son(v)}dp[j]\times(#{son(v)})!\times(#{son(v)}+1)$
記得維護$\mod 998244353$，可以直接全部都用$long\ long$運算
階乘可以預先維護一個陣列就好了

程式碼:

const int _n=2e5+10;  
ll t,n,u,v,dp[_n],fac[_n];  
VI G[_n];  
void dfs(int v,int fa){  
  if(SZ(G[v])==1 and G[v][0]==fa)dp[v]=1;  
  ll res=1;  
  rep(i,0,SZ(G[v]))if(fa!=G[v][i])dfs(G[v][i],v),res*=dp[G[v][i]],res%=mod;  
  res*=fac[SZ(G[v])],res%=mod;  
  dp[v]=res;  
}  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>n;rep(i,0,n-1){cin>>u>>v;u--,v--;G[u].pb(v),G[v].pb(u);}  
  fac[0]=1;rep(i,1,n+1)fac[i]=fac[i-1]*i%mod;  
  dfs(0,-1);cout<<dp[0]*n%mod<<'\n';  
  return 0;  
}  

標頭、模板請點Submission看
Submission