题目描述
定义无根树T的值为 ,其中V(T)是T的所有顶点的集合,而d(u)是T的度数。定义将森林的价值为森林中所有树的价值之和。求所有包含 N 个节点的森林的值的总和。
答案对读入的M取模。
输入描述
第一行输入两个整数T,M,T表示测试样例的数量,M表示需取模的数;
接下来T行每行输入一个整数N,表示森林共有N个节点。
输出描述
对于每个N输出一个对M取模的整数作为答案。
样例
- 输入
5 1000000007
2
3
4
5
107 - 输出
2
24
264
3240
736935633
题解思路
首先,根据prufer序列我们可以知道,对于一颗有n个节点的无根树,共可以形成 棵树。
prufer序列相关介绍:https://www.cnblogs.com/chenxiaoran666/p/prufer.html
不妨假设它的值为 ,n个节点的森林个数为
,那么可以得出:
随后就可以推出n个点可以形成的权值和:
但定睛一看,发现i对于这个式子并没有什么作用,于是可以简化为:
假定n个点可以形成的森林的权值和为 。
我们每次加入第n个点,再选择i个点与其形成一棵树。当选择i个点和第n个点时,就形成一棵有i+1个节点的树与之对应,对于每种方式,都能得到 的贡献。那么我们就能得到最终的式子:
由此就可以很轻松地得到最终的结果。
参考代码
#include <bits/stdc++.h> using namespace std; int n,fa[200010]; long long a[100050],b[100050],ls[200050],nt[200050]; long long ans,cnt; int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); } int main() { int T,cnT=0; scanf("%d",&T); while(T--) { scanf("%d",&n); cnt=0; for(int i=1;i<=n;i++) { scanf("%lld%lld",&a[i],&b[i]); ls[cnt++]=a[i]; ls[cnt++]=b[i]; } sort(ls,ls+cnt); cnt=unique(ls,ls+cnt)-ls; for(int i=1;i<=n;i++) { a[i]=lower_bound(ls,ls+cnt,a[i])-ls; b[i]=lower_bound(ls,ls+cnt,b[i])-ls; } for(int i=0;i<cnt;i++) { fa[i]=i; nt[i]=0; } for(int i=1;i<=n;i++) { if(find(a[i])!=find(b[i])) { nt[find(b[i])]|=nt[find(a[i])]; fa[find(a[i])]=find(b[i]); } else { nt[find(a[i])]=1; } } ans=cnt; for(int i=0;i<cnt;i++) if(find(i)==i&&!nt[find(i)]) ans--; printf("Case #%d: ",++cnT); printf("%lld\n",ans); } }