鏈接：https://ac.nowcoder.com/acm/contest/18072/E
題目：給你一棵n個節點的帶標號無根樹。每次，你可以選擇一個度數為1的節點并將它從樹上移除。問總共有多少種不同的方式能將這棵樹刪到只剩 1 個點。兩種方式不同當且僅當至少有一步被刪除的節點不同。

思路：首先我們把他看成有根樹來求解，一般我們以1為根，也就是說1結點是最后才去除的，我們以dp【i】來表示去除i子樹有多少種方式，dp[i]=?（v是i的兒子）;每次統計完答案以后都要sizei-sizev，很容易想到這個跟減的順序是沒有關系的。

現在我們統計完了有根樹的值，現在可以考慮來換根了，我們考慮從x->y，從x根轉化到y根，首先我們考慮一下回退，在y根中，?,;

根據這兩條公式已經可以進行換根，我們還可以化簡，把dp1[y]約掉；

代碼：

#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <cstdlib> #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define FILL(a,b) (memset(a,b,sizeof(a))) #define re register #define lson rt<<1 #define rson rt<<1|1 #define lowbit(a) ((a)&-(a)) #define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); #define fi first #define rep(i,n) for(int i=0;(i)<(n);i++) #define rep1(i,n) for(int i=1;(i)<=(n);i++) #define se second #define scd(a) scanf("%d",&a) #define scdd(a,b) scanf("%d%d",&a,&b) #define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c) #define ac cout<<ans<<"\n" #define F(x) ((x)/3+((x)%3==1?0:tb)) #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll> pii; int dx[4]= {-1,1,0,0},dy[4]= {0,0,1,-1}; const ll mod=998244353; const ll N =1e6+10; const double eps = 1e-4; //const double pi=acos(-1); int n; vector<int> g[N]; ll f[N],invf[N],inv[N]; ll dp[N]; ll son[N]; ll ans; int c(int x,int y){return (((f[x]*invf[x-y])%mod)*invf[y])%mod; } void dfs(int u,int p){son[u]=1;dp[u]=1;for(int v:g[u]){if(v==p) continue;dfs(v,u);son[u]+=son[v];}int s=son[u]-1;for(int v:g[u]){if(v==p) continue;dp[u]=(dp[u]*(c(s,son[v])*dp[v]%mod))%mod;s-=son[v];}//cout<<u<<" "<<dp[u]<<endl; } void DP(int u,int p){ans=(ans+dp[u])%mod;for(int v:g[u]){if(v==p) continue;dp[v]=dp[u]*invf[son[v]-1]%mod*f[son[v]]%mod;dp[v]=dp[v]*invf[n-son[v]]%mod;dp[v]=dp[v]*f[n-1-son[v]]%mod;DP(v,u);} } void sovle(){cin>>n;f[0]=f[1]=invf[0]=invf[1]=inv[1]=1;for(int i=2;i<=n;i++){f[i]=(f[i-1]*i)%mod;inv[i]=(mod-mod/i)*inv[mod%i]%mod;invf[i]=invf[i-1]*inv[i]%mod;}for(int i=1;i<n;i++){int x,y;cin>>x>>y;g[x].push_back(y);g[y].push_back(x);}dfs(1,0);//cout<<dp[1]<<endl;DP(1,0);cout<<ans; } int main() { #ifdef LOCALfreopen("in.txt", "r", stdin); #elseint t=1;// cin>>t;while(t--) sovle(); #endif // LOCALreturn 0; }

?

?

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的牛客挑战赛30 C 小G砍树 换根dp+组合的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。