hdu6810 Imperative Meeting

http://acm.hdu.edu.cn/showproblem.php?pid=6810

参照题解的做法，计算每条边的贡献，公式不想写了，这题其实是个组合数学题，比赛的时候还以为是树形DP

不过还挺难想到那个取min值转换成两个然后把i合并进去发现可以递推求这个东西。。。组合数学功底不足。。。

注意几个细节，首先是需要特判p=(m-1)/2>=1时，那个h[s]才>0，否则都是0

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int maxl=1e6+10;
const int mod=1e9+7;int n,m;ll p,ans;
int fa[maxl];
vector<int> e[maxl];
ll son[maxl],fac[maxl],inv[maxl],h[maxl],f[maxl];inline ll qp(ll a,ll b)
{ll ans=1,cnt=a;while(b){if(b&1)	ans=ans*cnt%mod;cnt=cnt*cnt%mod;b>>=1;}return ans;
}inline ll c(ll n,ll r)
{if(n<0 || r<0 || r>n) return 0;return fac[n]*inv[r]%mod*inv[n-r]%mod;
}inline void prework()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)e[i].clear(),son[i]=0;for(int i=2;i<=n;i++){scanf("%d",&fa[i]);e[fa[i]].push_back(i);e[i].push_back(fa[i]);}if(n==1)return;p=(m-1)/2;h[1]=c(n-1,m-1);if(p<1) h[1]=0;for(int i=2;i<=n-1;i++)h[i]=((h[i-1]-(c(i-2,p-1)*c(n-i,m-1-p)%mod))%mod+mod)%mod;for(int i=1;i<=n-1;i++){f[i]=(i*h[i]%mod+h[n-i]*(n-i)%mod)%mod;if(m%2==0)f[i]=(f[i]+c(i,m/2)*c(n-i,m/2)%mod*(m/2)%mod)%mod;}
}inline void dfs(int u,int fa)
{son[u]=1;for(int v:e[u]){if(v==fa) continue;dfs(v,u);son[u]+=son[v];ans=(ans+f[son[v]])%mod;}
}inline void mainwork()
{ans=0;dfs(1,0);
}inline void print()
{printf("%lld\n",ans);
}int main()
{fac[0]=1;for(int i=1;i<maxl;i++)fac[i]=fac[i-1]*i%mod;inv[maxl-1]=qp(fac[maxl-1],mod-2);for(int i=maxl-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;int t;scanf("%d",&t);for(int i=1;i<=t;i++){prework();mainwork();print();}return 0;
}