solution code of Valid Paths problem number-7 of may long challenge codechef

Valid Paths Problem Solution Code: CodeChef

Solution Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, a, b) for(int i=a; i<b; i++)
#define mod 1000000007
#define mk make_pair
#define uniq(v) (v).erase(unique(all(v)), (v).end())
#define ff first
#define ss second
#define rf(i, a, b) for(int i=a;i>=b;i--)
#define sc(a) scanf("%lld", &a)
#define pf printf
#define sz(a) (int)(a.size())
#define psf push_front
#define ppf pop_front
#define ppb pop_back
#define pb push_back
#define pq priority_queue
#define all(s) s.begin(),s.end()
#define sp(a) setprecision(a)
#define rz resize
#define ld long double
#define inf (ll)1e18
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define eb emplace_back
const double pi = acos(-1);

ll binpow(ll a, ll b, ll md){ll res = 1;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;}

ll ans;
vector<vector<int>> v;
vector<ll> dp, tot;
void dfs(int cur, int par)
{
    dp[cur]=1, tot[cur]=1;
    ll sum = 0, cnt = 0;
    f(i, 0, sz(v[cur]))
    {
        ll node = v[cur][i];
        if(node != par)
        {
            dfs(node, cur);
            dp[cur]+=((2*dp[node])%mod), dp[cur]%=mod, cnt++, tot[cur]+=tot[node], tot[cur]%=mod, tot[cur]+=dp[node], tot[cur]%=mod;
            sum += dp[node];
        }
    }
    f(i, 0, sz(v[cur]))
    {
        int node = v[cur][i];
        if(node != par)
        {
            tot[cur] += (dp[node]*((sum-dp[node]+mod)%mod))%mod;
            tot[cur] %= mod;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    int z = 1;
    cin>>z;
    f(i, 1, z+1)
    {
        ans = 0;
        int n;cin>>n;
        v.rz(n+1), dp.rz(n+1), tot.rz(n+1);
        f(i, 0, n-1)
        {
            int l, r;
            cin>>l>>r;
            v[l].pb(r), v[r].pb(l);
        }
        dfs(1, 1);
        ll ans = tot[1]%mod;
        cout<<ans<<endl;
        dp.clear(), v.clear(), tot.clear();
    }
}