Cod sursa(job #3369095)

Utilizator andrei.eEnachescu Andrei andrei.e Data 17 octombrie 2026 11:49:27
Problema A+B Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#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;
}