我太菜了，换根树DP竟然写了两个小时
考试的时候写了4个DP死活调不出来大样例
还是自己的心理素质不够好，本来一个简简单单的DP写得一团乱麻。。。
换根DP的思路就是：
（1）、先算出每个点子树内部的答案
（2）、此时根节点的DP值就是它在全局的答案，于是我们就需要从上往下DP，用父亲的DP值来更新儿子的DP值。
设f[u][k]表示树中到节点u距离小于等于k的节点个数
g[u][k]表示树中到节点u影响力为k时的拥挤程度
显然，（1）部分的转移方程就是：
（2）、部分的转移就比较恶心了。。。一定要理清思路
（注意，此时的f[u]用的是已经经历过第二次转移的值，但f[son]还没有经过第二次转移（也就是只统计了子树中的答案））
由于g[son][i]在之前是计算的子树中来到son的点的拥挤程度，所以在点计算g[son][i]的时候
它在之前是g[son][i]=f[son][i]*......
我们需要把f[son][i]换成全树中的f[son][i]，即除掉一个f[son][i]再乘一个f[son][i]+f[u][i-1]-f[son][i-2]
后面的g[u][i-1]也要做类似的换算
又因为g[u][i-1]在之前是重复统计了g[son][i-2]的答案的，所以我们又要把g[son][i-2]除掉
一定要注意转移的顺序啊啊啊啊啊啊！！！！！！
代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 100005 const int mod=1000000007; int ksm(int x,int y) { int ret=1; while(y){ if(y&1)ret=1ll*ret*x%mod; y>>=1;x=1ll*x*x%mod; } return ret; } int n,k; int fir[N],nxt[2*N],to[2*N],cnt; void adde(int a,int b) { to[++cnt]=b;nxt[cnt]=fir[a];fir[a]=cnt; to[++cnt]=a;nxt[cnt]=fir[b];fir[b]=cnt; } int f[N][12],tmp[N][12],g[N][12],fa[N]; void dfs1(int u) { for(int i=0;i<=k;i++) g[u][i]=f[u][i]=1; for(int v,p=fir[u];p;p=nxt[p]){ v=to[p]; if(v!=fa[u]){ fa[v]=u; dfs1(v); for(int i=1;i<=k;i++){ f[u][i]+=f[v][i-1]; g[u][i]=1ll*g[u][i]*g[v][i-1]%mod; } } } for(int i=0;i<=k;i++) g[u][i]=1ll*g[u][i]*f[u][i]%mod; } void dfs2(int u) { for(int v,p=fir[u];p;p=nxt[p]){ v=to[p]; if(v!=fa[u]){ for(int i=k;i>=1;i--){ g[v][i]=1ll*g[v][i]*ksm(f[v][i],mod-2)%mod*(f[v][i]+f[u][i-1]-(i>=2?f[v][i-2]:0))%mod *g[u][i-1]%mod*(i>=2?ksm(g[v][i-2],mod-2):1)%mod*ksm(f[u][i-1],mod-2)%mod *(f[u][i-1]-(i>=2?f[v][i-2]:0))%mod; f[v][i]+=f[u][i-1]-(i>=2?f[v][i-2]:0); } dfs2(v); } } } int main() { int i,u,v; scanf("%d%d",&n,&k); for(i=1;i<n;i++){ scanf("%d%d",&u,&v); adde(u,v); } dfs1(1);dfs2(1); for(i=1;i<=n;i++)printf("%d ",f[i][k]);printf("\n"); for(i=1;i<=n;i++)printf("%d ",g[i][k]); }
