Hackerearth DP C

//============================================================================
// Name        : ACM
// Author      : Tarango Khan
// Team        : BRACU Byteheads
//============================================================================

#include <bits/stdc++.h>
using namespace std;
#define Size 100005
#define Mod 1000000007
#define INF 999999999999999

struct Edge{
    int v;
    long long cost;
    Edge(int a,long long c){
        v = a;cost = c;
    }
};

int N;
long long sing[Size];
vector<Edge> Graph[Size];
long long DP[Size][2];

long long call(int cur,int cnt,int f,int prev){
    //printf("cur: %d , f: %d , prev: %d\n",cur,f,prev);
    if(DP[cur][f] != -1) return DP[cur][f];
    int Sz = Graph[cur].size();
    long long res = 0;
    if(f == 1){
        for(int i = 0;i<Sz;i++){
            Edge e = Graph[cur][i];
            if(e.v == prev) continue;
            long long ret1 = call(e.v,cnt,0,cur);
            long long ret2 = call(e.v,cnt+1,1,cur) + sing[e.v];
            res += min(ret1,ret2);
        }
    }else{
        if(Sz == 1 && prev != -1){
            res = sing[cur];
        }else{
            long long ans1 = 0,ans2 = INF;
            for(int i = 0;i<Sz;i++){
                Edge e = Graph[cur][i];
                if(e.v == prev) continue;
                ans1 += call(e.v,cnt,0,cur) + sing[cur];
            }
            long long sum = 0;
            for(int i = 0;i<Sz;i++){
                Edge e = Graph[cur][i];
                if(e.v == prev) continue;
                sum += call(e.v,cnt,0,cur);
            }
            for(int i = 0;i<Sz;i++){
                Edge e = Graph[cur][i];
                if(e.v == prev) continue;
                long long ret1 = sum + call(e.v,cnt+1,1,cur) + e.cost - call(e.v,cnt,0,cur);
                ans2 = min(ans2,ret1);
            }
            res = min(ans1,ans2);
        }
    }
    //printf("  -> From %d , f: %d , res: %lld\n",cur,f,res);
    return DP[cur][f] = res;
}

long long call2(int cur,int prev){
    long long res = 1;
    if(DP[cur][0] == DP[cur][1]) res++;
    int Sz = Graph[cur].size();
    for(int i = 0;i<Sz;i++){
        Edge e = Graph[cur][i];
        if(e.v == prev) continue;
        res  = (res * call2(e.v,cur))%Mod;
    }
    return res;
}

int main() {
    int u,v;
    long long c;
    scanf("%d",&N);
    for(int i = 0;i<N;i++){
        scanf("%lld",&sing[i]);
    }
    for(int i = 0;i<N-1;i++){
        scanf("%d %d %lld",&u,&v,&c);
        u--;v--;
        Graph[u].push_back(Edge(v,c));
        Graph[v].push_back(Edge(u,c));
    }
    memset(DP,-1,sizeof(DP));
    long long res1 = call(0,0,0,-1);
    long long res2 = call2(0,-1)%Mod;
    printf("%lld %lld\n",res1,res2);
    return 0;
}
Language: C++