题目链接：Who killed Cock Robin
题目描述：
Who killed Cock Robin?
I, said the Sparrow, With my bow and arrow,I killed Cock Robin.
Who saw him die?
I, said the Fly.With my little eye,I saw him die.
Who caught his blood?
I, said the Fish,With my little dish,I caught his blood.
Who’ll make his shroud?
I, said the Beetle,With my thread and needle,I’ll make the shroud.
…
All the birds of the air
Fell a-sighing and a-sobbing.
When they heard the bell toll.
For poor Cock Robin.
March 26, 2018
Sparrows are a kind of gregarious animals,sometimes the relationship between them can be represented by a tree.
The Sparrow is for trial, at next bird assizes,we should select a connected subgraph from the whole tree of sparrows as trial objects.
Because the relationship between sparrows is too complex, so we want to leave this problem to you. And your task is to calculate how many different ways can we select a connected subgraph from the whole tree.
输入描述：
输出描述：
题目分析：
一开始我以为用并查集可以做出来，后面做着做着就发现不行，因为这是树，不是图，那么得换个思路了。
仔细想想，我们可以用树形dp来做，定义一个数组dp[i]表示所有以根节点为i的子图的个数，如果根节点i有k个子树，那么dp[i]就等于(dp[1]+1)✖(dp[2]+1)✖…dp[k]+1,为啥要加1呢？ 因为子树子图数为0也是一种情况！后面就用dfs来更新dp数组了，记得要在语句中判断当前dp[i]是否已经算过了，这能减少很多复杂度。
时间复杂度：O(n）
代码：
#include<bits/stdc++.h> using namespace std; const int N=2e5+10,mod=1e7+7; typedef long long ll; int dp[N],n; vector<int> edges[N]; ll ans=0; ll dfs(int x) { dp[x]=1; ll res=1; for(int i=0;i<edges[x].size();i++) { int t=edges[x][i]; if(dp[t]) continue; res=(res*(dfs(t)+1))%mod; } dp[x]=res; return res; } int main() { scanf("%d",&n); for(int i=1;i<=n-1;i++) { int u,v; scanf("%d%d",&u,&v); edges[u].push_back(v); edges[v].push_back(u); } dfs(1); for(int i=1;i<=n;i++) ans=(ans+dp[i])%mod; cout<<ans<<endl; return 0; } 讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/129438.html