唔感觉这几天换根用的好多啊，所以换根dp还是打一下好了。（虽然觉得一道题不大够的亚子）
所以大佬们有什么换根好题可以推荐一下的嗷！
这道题因为对于每一个点都要统计答案，所以要换根。
我们先考虑对于一个根我们怎么求出答案。
因为每个点到根的路径上只能有一条不良道路。
设f[i]为以i为根的子树内分配不良道路的方案数。
现在就有两种情况：
1. i 到son那条边是不良道路，那么以 i 为根的子树内都不会是不良道路。
2.i 到son那条边不是不良道路，那么加上f[son]。
所以答案为f[son]+1的累乘。
接下来考虑换根：
发现当根从 i 变成 j 的某个孩子时，变化的只有f[i]和f[j]。
f[i]会除掉关于 j 的贡献，f[j]会乘上 i 的贡献。
因为除的时候不一定会有逆元，这里我们使用前缀积和后缀积的方式处理。
具体看代码吧。
#include<bits/stdc++.h> #define N 200003 #define LL long long #define INF 2100000000 #define mod 1000000007 using namespace std; int read() { int x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f; } void print(int x) { if(x<0)putchar(‘-‘),x=-x; if(x>9)print(x/10); putchar(x%10+‘0‘); } struct EDGE{ int nextt,to; }w[N*2]; int tot=0; int head[N]; void add(int a,int b) { tot++; w[tot].nextt=head[a]; w[tot].to=b; head[a]=tot; } int n; LL f[N],ans[N]; vector<LL>qzj[N],hzj[N]; void dfs1(int x,int fa) { f[x]=1; for(int i=head[x];i;i=w[i].nextt) { int v=w[i].to; if(v==fa)continue; dfs1(v,x); f[x]=(f[x]*(f[v]+1)%mod)%mod; } } void dfs2(int x,int fa)//换根 { ans[x]=1; for(int i=head[x];i;i=w[i].nextt) { int v=w[i].to; ans[x]=(ans[x]*(f[v]+1)%mod)%mod; if(v!=fa) { qzj[x].push_back(f[v]+1); hzj[x].push_back(f[v]+1); } } for(int i=1;i<qzj[x].size();++i)qzj[x][i]=qzj[x][i]*qzj[x][i-1]%mod; for(int i=hzj[x].size()-2;i>=0;--i)hzj[x][i]=hzj[x][i]*hzj[x][i+1]%mod; int cnt=0; for(int i=head[x];i;i=w[i].nextt) { int v=w[i].to; if(v==fa)continue; f[x]=fa?(f[fa]+1):1; if(cnt>0)f[x]=f[x]*qzj[x][cnt-1]%mod; if(cnt<hzj[x].size()-1)f[x]=f[x]*hzj[x][cnt+1]%mod; dfs2(v,x);cnt++; } } int main() { n=read(); for(int i=2;i<=n;++i) { int x=read(); add(x,i);add(i,x); } dfs1(1,0); dfs2(1,0); for(int i=1;i<=n;++i)printf("%lld ",ans[i]); } /* */
原文：https://www.cnblogs.com/yyys-/p/11845001.html
