题目链接：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; } 