Pagini recente » Cod sursa (job #3369084) | Cod sursa (job #3369078) | Cod sursa (job #3369076) | Cod sursa (job #3369096) | Cod sursa (job #3369095)
#include <vector>
#include <iostream>
#include <stack>
#include <algorithm>
#include <queue>
#include <fstream>
#include <iomanip>
#include <map>
#include <cmath>
#include <set>
#include <string>
using namespace std;
// programare dinamica
// rezolv problem x
// gasim subprobleme y
// folosim solutiile de la subprobleme y
// ca sa rezolvam problema x
// dp[n] = costul minim sa ajungem de la 1 la n
// dp[n] = min (dp[n - 1] + cost(n - 1, n), dp[n - 2] + cost(n - 2, n))
// dp[1] = 0
const int MOD=1e9+7;
int n, p, dp[100'005][2],m;
vector <int> adj[100'005];
void dfs(int node,int p)
{
dp[node][1]=1;
dp[node][0]=1;
for(int i=0;i<adj[node].size();++i)
{
if(adj[node][i]!=p)
{
dfs(adj[node][i],node);
dp[node][1]=(1LL*(dp[adj[node][i]][1]+dp[adj[node][i]][0])%MOD*dp[node][1])%MOD;
dp[node][0]=(1LL*(dp[adj[node][i]][1])*dp[node][0])%MOD;
}
}
}
// dim(node) = 1 + \sum dim(copil_nod)
int main()
{
int c;
cin >> n;
for (int i = 1; i <n; i ++)
{
cin >> p;
cin >>c;
adj[p].push_back(c);
adj[c].push_back(p);
}
dfs(1,1);
cout<<(dp[1][1]+dp[1][0])%MOD;
return 0;
}