---
title: Codeforce 1172 B. Nauuo and Circle 解析(思維、DP)
description: "Codeforce 1172 B. Nauuo and Circle 解析(思維、DP)"
disqus: hackmd
---
<meta name="robots" content="Codeforce 1172 B. Nauuo and Circle 解析(思維、DP)">
<!-- toc -->

# Codeforce 1172 B. Nauuo and Circle 解析(思維、DP)
今天我們來看看CF1172B
[題目連結](https://codeforces.com/problemset/problem/1172/B)

> **題目**
略，請直接看原題

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

### 想法
這題的重點是要想到:一個節點$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](https://codeforces.com/contest/1172/submission/91128597)