题目链接
题意：
给定一棵$n$个节点的无根树，可以对边黑白染色。求对于每个点有多少种染色方案，使得它到任意点的路径上至多经过一条黑边。对$10^9+7$取模。
$1\le n \le 10^5$
分析：
可以看出，这题就是把每个点做根的情况都求一遍。
先来看链的情况：以$i$号点做根，那么左侧的边总共只能有一条染黑；右侧同理。由乘法原理可得答案为$i\times (n-i+1)$。
考虑树形DP。假设确定$1$号点为根节点，设$f_i$表示由下至上$i$点及其子树的答案，那么很容易得到$$f_i=\prod\limits_{j\in son_i} ( f_j+1 )$$
算法是儿子到父亲的这条边染不染黑。染了那么整棵子树都不能再染，不染就是直接传子树答案。兄弟之间对父亲的贡献互不干扰，所以要乘起来。
现在来考虑怎么换根。
发现我们的答案和深度无关，同一棵子树的贡献总是一定的，考虑记忆化。
但是换根之后树的形态发生变化，不能用点代表子树。
发现点不能代表子树的原因是遍历子树的方向会有不同。即：可以用不同的边进入同一点。
那么就可以对边记忆化。完成！
实现：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define IL inline
using namespace std;
typedef long long LL;
const int N=
1e5;
const int mod=1e9+
7;
int n,p[N+
3];
struct Edge{
int to,nxt;
}e[N*
2+
3];
int h[N+
3],top;
IL void adde(
int u,
int v){
top++
;
e[top].to=
v;
e[top].nxt=
h[u];
h[u]=
top;
}
bool vis[N+
3],mrk[N*
2+
3];
LL f[N*
2+
3];
LL dfs(int u){
LL ret=
1LL;
for(
int i=h[u];~i;i=
e[i].nxt){
int v=
e[i].to;
if(vis[v])
continue;
vis[v]=
true;
if(!
mrk[i]){
mrk[i]=
true;
f[i]=
dfs(v);
}
ret=ret*(f[i]+
1)%
mod;
}
return ret;
}
int main(){
freopen("tree.in",
"r",stdin);
freopen("tree.out",
"w",stdout);
scanf("%d",&
n);
top=-
1;
memset(h,-
1,
sizeof h);
for(
int i=
2;i<=n;i++
){
scanf("%d",&
p[i]);
adde(i,p[i]);
adde(p[i],i);
}
bool flag3=
true;
for(
int i=
2;i<=n&&flag3;i++
)
if(p[i]!=i-
1)
flag3=
false;
if(flag3){
for(
int i=
1;i<=n;i++
)
printf("%lld ",(LL)i*(n-i+
1)%
mod);
return 0;
}
memset(mrk,0,
sizeof mrk);
for(
int i=
1;i<=n;i++
){
memset(vis,0,
sizeof vis);
vis[i]=
true;
printf("%lld ",dfs(i));
}
return 0;
}
View Code
小结：
没什么好说的。认真水题吧。
转载于:https://www.cnblogs.com/Hansue/p/11408033.html
相关资源：JAVA上百实例源码以及开源项目
