冷水江市建设局网站,电子商务网站盈利模式,带有flash的网站,长垣有做网站设计的吗第四题#xff1a;T4树的覆盖
标签#xff1a;树、最小点覆盖、树形 d p dp dp题意#xff1a;求树的最小点覆盖集的大小和对应的数量#xff0c;数量对 1 , 000 , 000 , 007 1,000,000,007 1,000,000,007取余数。所谓覆盖集#xff0c;是该树的点构成的集合#xff0c;…第四题T4树的覆盖
标签树、最小点覆盖、树形 d p dp dp题意求树的最小点覆盖集的大小和对应的数量数量对 1 , 000 , 000 , 007 1,000,000,007 1,000,000,007取余数。所谓覆盖集是该树的点构成的集合对树上每一条边至少有一个顶点属于该集合。某个特定覆盖集的大小就是该集合中点的数量。题解第一问最小点覆盖集的大小比较好求也是非常经典的一个模型和上题树形 d p dp dp差不多对于每个节点 u u u分一下两种情况
dp[u][0]表示节点u属于点覆盖集且以点u为根的子树中所连接的边都被覆盖的情况下点覆盖集中所包含最少点的个数。
dp[u][1]表示点u不属于点覆盖集并且以点u为根的子树中所连接的边都被覆盖的情况下点覆盖集中所包含最少点的个数。以第二个样例举例 4 4 4、 5 5 5、 6 6 6这三个节点很显然选和不选到覆盖集分别是 1 1 1和 0 0 0。对于 2 2 2这个节点来说如果选了那么 2 2 2到 5 5 5这条边可以直接覆盖我们加上节点 5 5 5不选的情况 d p [ 5 ] [ 1 ] dp[5][1] dp[5][1]如果不选那么 2 2 2到 5 5 5这条边得通过选节点 5 5 5即加上 d p [ 5 ] [ [ 0 ] dp[5][[0] dp[5][[0]。
对应节点 3 3 3同理然后回到节点 1 1 1来看我们可以把节点 1 1 1选了那么节点 2 、 3 、 4 2、3、4 2、3、4选和不选无所谓了反正节点 1 1 1能覆盖到和他们对应的边不选节点 1 1 1那么节点 2 、 3 、 4 2、3、4 2、3、4都得选上即加上 d p [ 2 ] [ 0 ] d p [ 3 ] [ 0 ] d p [ 4 ] [ 0 ] dp[2][0]dp[3][0]dp[4][0] dp[2][0]dp[3][0]dp[4][0]。
总结一下
对于第一种状态 d p [ u ] [ 0 ] dp[u][0] dp[u][0]等于每个孩子节点的两种状态的最小值之和加 1 1 1即 d p [ u ] [ 0 ] 1 Σ m i n ( d p [ v ] [ 0 ] , d p [ v ] [ 1 ] ) ( f a [ v ] u ) dp[u][0]1Σmin(dp[v][0],dp[v][1]) \ (fa[v]u) dp[u][0]1Σmin(dp[v][0],dp[v][1]) (fa[v]u)对于第二种状态 d p [ u ] [ 1 ] dp[u][1] dp[u][1]等于每个孩子节点的第一种状态之和即 d p [ u ] [ 1 ] Σ d p [ v ] [ 0 ] ( f a [ v ] u ) dp[u][1]Σdp[v][0] \ (fa[v]u) dp[u][1]Σdp[v][0] (fa[v]u)
第二问求最小覆盖集的数量对于每个节点 u u u分一下两种情况
cnt[u][0]表示节点u属于点覆盖集以点u为根的子树当前最小覆盖集的数量
cnt[u][1]表示点u不属于点覆盖集以点u为根的子树当前最小覆盖集的数量c n t [ u ] [ 1 ] cnt[u][1] cnt[u][1]的状态转移方程比较好想它的所有孩子节点都得选进覆盖集所以对所以孩子节点的 c n t [ v ] [ 0 ] cnt[v][0] cnt[v][0]做一个乘积。即 c n t [ u ] [ 1 ] c n t [ u ] [ 1 ] ∗ c n t [ v ] [ 0 ] cnt[u][1] cnt[u][1] * cnt[v][0] cnt[u][1]cnt[u][1]∗cnt[v][0] c n t [ u ] [ 0 ] cnt[u][0] cnt[u][0]我们得去考虑对于孩子节点 v v v来说是选还是不选能够获得更小的覆盖集大小如果都能得都加起来做一个乘积否则从更小的情况转移过来做乘积。详情看代码部分可以自己再推导下
代码
#include bits/stdc.h
using namespace std;typedef long long ll;
const ll mod 1e9 7;
vectorll e[200005];
ll n, x, dp[200005][2], cnt[200005][2];void dfs(ll u) {dp[u][0] 1;dp[u][1] 0;cnt[u][0] cnt[u][1] 1;for (ll i 0; i e[u].size(); i) {ll v e[u][i];dfs(v);if (dp[v][0] dp[v][1]) cnt[u][0] cnt[u][0] * (cnt[v][0] cnt[v][1]) % mod;else if (dp[v][0] dp[v][1]) cnt[u][0] cnt[u][0] * cnt[v][0] % mod;else if (dp[v][0] dp[v][1]) cnt[u][0] cnt[u][0] * cnt[v][1] % mod;cnt[u][1] cnt[u][1] * cnt[v][0] % mod;dp[u][0] min(dp[v][0], dp[v][1]);dp[u][1] dp[v][0];}
}int main() {cin n;for (int i 2; i n; i) {cin x;e[x].push_back(i);}dfs(1);cout min(dp[1][0], dp[1][1]) endl;if (dp[1][0] dp[1][1]) cout (cnt[1][0] cnt[1][1]) % mod endl;else if (dp[1][0] dp[1][1]) cout cnt[1][0] % mod endl;else if (dp[1][0] dp[1][1]) cout cnt[1][1] % mod endl;return 0;
}
