题目链接：
codeforces 543D
题目大意：
给出一棵树，问如果以某个点为首都，满足这个点到达其他点路径上最多有一条坏路的方案数。
题目分析：
首先我们把点1当作根，然后我们定义dp[u]为以1为根的树u的子树是合法的且存在坏路的方案数。那么我们容易得到如下的转移方程，我们设u的孩子的集合为V。那么：
dp[u]=∏v∈V(dp[v]+1)
解释：如果当前是好路，那么子树中只要合法就好，如果当前路是坏路，那么子树中必须必须全是好路
dp[u]就是就是u为根的方案数，但是我们如果每个点都做一遍的话，复杂度是 O(n2) ,所以我们要想办法利用固定根的方法，通过转化的方法直接获得其他点作为根的情况。我们假设ans[u]为点u作为根的情况的方案数，p为u节点的父亲。我们可以得到：
ans[u]=(ans[p]dp[u]+1+1）⋅∏v∈V(dp[v]+1)
解释：当前点的方案数就相当于它的父亲去掉它自身作为子树的情况与它的儿子为根的情况之积
但是在出现 0的逆元的情况时，我们不能得到结果。所以采用 前缀和或 后缀和的方法来替代，我们定义up[u]数组表示以u为根，u之前的父亲为根的子树的全部情况。L[i]表示前i个儿子的方案数之积，R[i]表示后面n到i的序号的儿子的方案数之积。那么我们得到新的公式：
up[u]=L[i−1]⋅R[i+1]+1
ans[u]=up[u]⋅dp[u]
AC代码：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#define MAX 200007
using namespace std;
typedef long long LL;
int n;
LL dp[MAX];
LL L[MAX];
LL R[MAX];
LL ans[MAX];
vector<int> e[MAX];
const LL mod = 1000000007;
void add ( int u , int v )
{
e[u].push_back ( v );
e[v].push_back ( u );
}
void dfs1 ( int u , int p )
{
dp[u] = 1;
for ( int i = 0 ; i < e[u].size() ; i++ )
{
int v = e[u][i];
if ( v == p ) continue;
dfs1 ( v , u );
dp[u] *= dp[v]+1;
dp[u] %= mod;
}
}
LL inv ( LL num , LL n )
{
LL ret = 1;
while ( n )
{
if ( n&1 )
{
ret *= num;
ret %= mod;
}
num *= num;
num %= mod;
n >>= 1;
}
return ret;
}
void dfs2 ( int u , int p )
{
if ( p == -1 ) ans[u] = dp[u];
else ans[u] = (ans[p]*inv ( dp[u]+1 , mod-2 )%mod +1LL)%mod;
for ( int i = 0 ; i < e[u].size() ; i++ )
{
int v = e[u][i];
if (v == p ) continue;
if ( p != -1 )
{
ans[u] *= (dp[v]+1);
ans[u] %= mod;
}
}
for ( int i = 0 ; i < e[u].size() ; i++ )
{
int v = e[u][i];
if ( v == p ) continue;
dfs2 ( v , u );
}
}
void dfs3 ( int u , int p )
{
if ( p == -1 ) ans[u] = 1;
L[0] = 1;
R[e[u].size()-1] = ans[u];
for ( int i = 0 ; i < e[u].size() ; i++ )
{
int v = e[u][i];
if ( v == p )
{
L[i+1] = L[i];
continue;
}
L[i+1] = L[i]*(dp[v]+1)%mod;
}
for ( int i = e[u].size()-1 ; i > 0 ; i-- )
{
int v = e[u][i];
if ( v == p )
{
R[i-1] = R[i];
continue;
}
R[i-1] = R[i]*(dp[v]+1)%mod;
}
for ( int i = 0 ; i < e[u].size() ;i++ )
{
int v = e[u][i];
if ( v == p ) continue;
ans[v] = (L[i]*R[i]%mod+1)%mod;
}
for ( int i = 0 ;i < e[u].size() ; i++ )
{
int v = e[u][i];
if ( v == p ) continue;
dfs3 ( v , u );
}
}
int main ( )
{
int x;
while ( ~scanf ( "%d" , &n ))
{
for ( int i = 0 ; i <= n ; i++ )
e[i].clear();
for ( int i = 2 ; i <= n ; i++ )
{
scanf ( "%d" , &x );
add ( i , x );
}
dfs1 ( 1 , -1 );
//dfs2 ( 1 , -1 );
dfs3 ( 1 , -1 );
//for ( int i = 1 ; i <= n ; i++ )
// printf ( "%I64d " , ans[i] );
for ( int i = 1 ; i <= n ; i++ )
{
//cout << i << " : " << ans[i] <<" " << dp[i] << endl;
printf ( "%I64d " , ans[i]*dp[i]%mod );
}
puts ( "" );
}
}
最后
以上就是高高盼望最近收集整理的关于codeforces 543D D. Road Improvement(树形dp)的全部内容，更多相关codeforces内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复