原题链接https://ac.nowcoder.com/acm/contest/5672/I


题目描述

定义无根树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);
    }
}