2 樹

2.1 題目描述

給一棵n 個節點的樹，節點分別編號為0 到n - 1。
你可以通過如下的操作來修改這棵樹：首先先刪去樹上的一條邊，此時樹
會分裂為兩個連通塊，然后在兩個連通塊之間加上一條新的邊使得它們變成一
棵新的樹。
問有多少棵n 個節點的樹可以通過對原樹進行不超過k 次這樣的操作來
得到，答案對109 + 7 取模。如果有一條邊(u; v) 出現在了樹A 中且不在樹B
中，我們就認為樹A 和樹B 是不同的。
2.2 輸入格式
第一行為兩個整數n; k。
接下來一行用n - 1 個整數a1; a2; a3; :::; an-1 描述給定的樹。其中ai 表
示節點i 和節點ai 之間有一條邊，保證ai < i。
2.3 輸出格式
輸出一個整數表示答案對109 + 7 取模后的值。

2.4 輸入樣例一
3 1
0 0

2.5 輸出樣例一
3

?

2.6 輸入樣例二
6 4
0 1 1 3 3

2.7 輸出樣例二
1196

?

2.8 輸入樣例三
20 10
0 0 1 1 3 2 3 0 1 7 5 9 4 0 6 15 14 10 15

2.9 輸出樣例三
540101309

?

2.10 數據范圍與約定
對于100% 的數據，n<=80，k<n。

?

當時考試的時候先做的T1和T3然后就沒時間做這個題了，，，

但是可能當時我有時間也做不出來吧23333.

?

正解是矩陣樹定理+高斯消元/拉格朗日插值法。

因為最多只能選k條不是原來樹上的邊，所以我們可以把樹邊看成1，把非樹邊看成x。

最后的答案就是矩陣樹定理消出的多項式的x^k及之前的項的系數和。

?

這個當然可以暴力多項式乘法(因為多項式的項數不多但是有很多多項式要相乘，所以此時的NTT是沒有暴力快的)，

但是這樣太慢了，大數據會掛。

?

我們還可以發現最后的多項式是一個n-1次多項式，所以我們可以帶n對點來確定這個多項式。

這樣的復雜度是 O(N^4) ，開開心心過本題。。。

?

?

#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=87; const int ha=1000000007; int n,k,a[maxn][maxn]; int fa,b[maxn][maxn]; int c[maxn][maxn],ans;inline int add(int x,int y){x+=y;return x>=ha?x-ha:x; }inline int ksm(int x,int y){int an=1;for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha;return an; }inline int matrix_tree(int x){int an=1;memset(b,0,sizeof(b));for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){if(a[i][j]) b[i][j]=b[j][i]=ha-1,b[i][i]++,b[j][j]++;else b[i][j]=b[j][i]=ha-x,b[i][i]+=x,b[j][j]+=x;}for(int i=1;i<n;i++){int tmp=i;for(;tmp<n;tmp++) if(b[tmp][i]) break;if(tmp>i){an=ha-an;for(int k=i;k<n;k++) swap(b[i][k],b[tmp][k]);}for(int j=i+1;j<n;j++)while(b[j][i]){an=ha-an;int A=b[i][i]/b[j][i];for(int k=i;k<n;k++){b[i][k]=((ll)b[i][k]-b[j][k]*(ll)A)%ha;if(b[i][k]<0) b[i][k]+=ha;swap(b[i][k],b[j][k]);}}an=an*(ll)b[i][i]%ha;}return an; }inline void xy(){n++;for(int i=1;i<n;i++){if(!c[i][i]){for(int j=i+1;j<n;j++) if(c[j][i]){for(int k=i;k<=n;k++) swap(c[j][k],c[i][k]);break;}}for(int j=i+1;j<n;j++)while(c[j][i]){int A=c[i][i]/c[j][i];for(int k=i;k<=n;k++){c[i][k]=((ll)c[i][k]-c[j][k]*(ll)A)%ha;if(c[i][k]<0) c[i][k]+=ha;swap(c[i][k],c[j][k]);}}}for(int i=n-1;i;i--){for(int j=n-1;j>i;j--) c[i][n]=add(c[i][n],add(ha,-c[j][n]*(ll)c[i][j]%ha));c[i][n]=c[i][n]*(ll)ksm(c[i][i],ha-2)%ha;} }int main(){freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);scanf("%d%d",&n,&k);for(int i=2;i<=n;i++){scanf("%d",&fa);fa++,a[i][fa]++,a[fa][i]++;}for(int i=1;i<=n;i++){for(int j=1,u=1;j<=n;j++,u=u*(ll)i%ha) c[i][j]=u;c[i][n+1]=matrix_tree(i);}xy();k++;for(int i=1;i<=k;i++) ans=add(ans,c[i][n]);printf("%d\n",ans);return 0; }

　　

轉載于:https://www.cnblogs.com/JYYHH/p/8507389.html

總結

以上是生活随笔為你收集整理的某考试 T2 Tree的全部內容，希望文章能夠幫你解決所遇到的問題。

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