HackerEarth The Battle of Panipat problem solution

In this HackerEarth The Battle of Panipat problem solution This is 1526 A.D. Third Battle of Panipat between Babur and Ibrahim Lodi, the current ruler of India is going on.

Realising that Lodi has much larger army, Babur planned to attack the cities of India to bring the moral of the soldiers of Lodi down.

Now, Lodi had been ordered by his ancestors that, if he is to rule India, the cities in India should be connected and this system should always form a tree.

Now, in 1526, India had N cities(numbered 0 to N-1) all connected by roads and the whole system formed a tree. Lodi had to plan to save his cities. So he decided to use his special power S.H.I.E.L.D. And since all the other cities would be destroyed he wanted the protected cities system should form a tree.

S.H.I.E.L.D was an expensive power and Lodi decided that he would use it only on some specific cities. Now you being the prime minister of the ruler, need to tell him in how many ways he can do this. Lodi may even not use this power at all on any city or he may even select all the cities.

HackerEarth The Battle of Panipat problem solution.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<vector>
#include<cassert>
#include<sstream>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
#define llu long long unsigned int
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define rep(i,b) for(i=0;i<b;i++)
#define mod 1000000007
#define pin(n) printf("%llun",n)
typedef pair<llu,llu> PII;
typedef vector<llu> VI;
VI degree[1000000];
int visited[1000000]={};
PII f(llu v)
{
    llu i;
    visited[v]=1;
    PII ret = mp(1,0);
    rep(i,degree[v].size())
    {
        if(visited[degree[v][i]]==0)
        {
            PII pr = f(degree[v][i]);
            ret.F = (ret.F*(pr.F + 1))%mod;
            ret.S = (ret.S+(pr.F + pr.S))%mod;
        }
    }
    return ret;
}
int main()
{
    llu n,i,x,y;
    scanf("%llu",&n);
    rep(i,n-1)
    {
        scanf("%llu%llu",&x,&y);
        degree[x].pb(y);
        degree[y].pb(x);
    }
    PII pr = f(0);
    pin((pr.F + pr.S + 1)%mod);
    return 0;
}

coding problems solutions