原题链接：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);
    }
}