HackerRank Road Maintenance problem solution

In this HackerRank Road, Maintenance problem solution Byteland has N cities (numbered from 1 to N) and N – 1 bidirectional road. A path is comprised of 1 or more connected roads. It is guaranteed that there is a path from any city to any other city.

Steven is a road maintenance worker in Byteland. He is required to maintain exactly M paths on any given workday. He cannot work on the same road twice in one day (so no 2 paths can contain the same 2 roads). Steven can start his workday in any city and, once he has finished maintaining a path, teleport to his next starting city.

Given M, help Steven determine how many different possible M-path sets will allow him to perform his maintenance duties.

Problem solution in Java.

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class D {
    InputStream is;
    PrintWriter out;
    String INPUT = "";
    
    void solve()
    {
        int n = ni(), m = ni();
        int[] from = new int[n - 1];
        int[] to = new int[n - 1];
        for (int i = 0; i < n - 1; i++) {
            from[i] = ni() - 1;
            to[i] = ni() - 1;
        }
        int[][] g = packU(n, from, to);
        int[][] pars = parents3(g, 0);
        int[] par = pars[0], ord = pars[1], dep = pars[2];
        int mod = 1000000007;
        int[][] fif = enumFIF(100, mod);
        long[] sel = new long[100];
        long i2 = invl(2, mod);
        for(int i = 0;i < 100;i++){
            long u = fif[0][i] * (long)fif[1][i/2] % mod;
            for(int j = 0;j < i/2;j++)u = u * i2 % mod;
            sel[i] = u;
        }
        long[][] seab = new long[100][100];
        for(int i = 0;i < 100;i++){
            for(int j = 0;j <= i;j++){
                seab[i][j] = C(i, j, mod, fif) * sel[i-j] % mod;
            }
        }
        
        long[][] dp0 = new long[n][m+1];
        long[][] dp1 = new long[n][m+1];
        for(int i = n-1;i >= 0;i--){
            int cur = ord[i];
            long[][] ldp = new long[m+1][2*m+1];
            ldp[0][0] = 1;
            for(int e : g[cur]){
                if(par[cur] != e){
                    long[][] nldp = new long[m+1][2*m+1];
                    for(int j = 0;j <= m;j++){
                        for(int k = 0;k <= 2*m;k++){
                            if(ldp[j][k] == 0)continue;
                            for(int l = 0;j+l <= m;l++){
                                nldp[j+l][k] += dp0[e][l] * ldp[j][k];
                                nldp[j+l][k] %= mod;
                                if(k+1 <= 2*m){
                                    nldp[j+l][k+1] += dp1[e][l] * ldp[j][k];
                                    nldp[j+l][k+1] %= mod;
                                }
                            }
                        }
                    }
                    ldp = nldp;
                }
            }
            for(int j = 0;j <= m;j++){
                for(int k = 0;k <= 2*m;k++){
                    for(int ab = k%2;ab <= k;ab+=2){
                        int nj = j+(k+ab)/2;
                        if(nj <= m){
                            dp0[cur][nj] += ldp[j][k] * seab[k][ab];
                            dp0[cur][nj] %= mod;
                        }else{
                            break;
                        }
                    }
                    for(int ab = (k%2)^1;ab <= k+1;ab+=2){
                        int nj = j+(k+ab)/2;
                        if(nj <= m){
                            long w = k-1 >= 0 ? k * seab[k-1][ab] : 0;
                            if(ab-1 >= 0)w += seab[k][ab-1];
                            dp1[cur][nj] += ldp[j][k] * (w%mod);
                            dp1[cur][nj] %= mod;
                        }else{
                            break;
                        }
                    }
                }
            }

        }
        out.println(dp0[0][m]);
    }
    
    public static long C(int n, int r, int mod, int[][] fif) {
        if (n < 0 || r < 0 || r > n)
            return 0;
        return (long) fif[0][n] * fif[1][r] % mod * fif[1][n - r] % mod;
    }
    
    public static long invl(long a, long mod) {
        long b = mod;
        long p = 1, q = 0;
        while (b > 0) {
            long c = a / b;
            long d;
            d = a;
            a = b;
            b = d % b;
            d = p;
            p = q;
            q = d - c * q;
        }
        return p < 0 ? p + mod : p;
    }
    
    public static int[][] enumFIF(int n, int mod) {
        int[] f = new int[n + 1];
        int[] invf = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            f[i] = (int) ((long) f[i - 1] * i % mod);
        }
        long a = f[n];
        long b = mod;
        long p = 1, q = 0;
        while (b > 0) {
            long c = a / b;
            long d;
            d = a;
            a = b;
            b = d % b;
            d = p;
            p = q;
            q = d - c * q;
        }
        invf[n] = (int) (p < 0 ? p + mod : p);
        for (int i = n - 1; i >= 0; i--) {
            invf[i] = (int) ((long) invf[i + 1] * (i + 1) % mod);
        }
        return new int[][] { f, invf };
    }

    public static int[][] parents3(int[][] g, int root) {
        int n = g.length;
        int[] par = new int[n];
        Arrays.fill(par, -1);

        int[] depth = new int[n];
        depth[0] = 0;

        int[] q = new int[n];
        q[0] = root;
        for (int p = 0, r = 1; p < r; p++) {
            int cur = q[p];
            for (int nex : g[cur]) {
                if (par[cur] != nex) {
                    q[r++] = nex;
                    par[nex] = cur;
                    depth[nex] = depth[cur] + 1;
                }
            }
        }
        return new int[][] { par, q, depth };
    }

    static int[][] packU(int n, int[] from, int[] to) {
        int[][] g = new int[n][];
        int[] p = new int[n];
        for (int f : from)
            p[f]++;
        for (int t : to)
            p[t]++;
        for (int i = 0; i < n; i++)
            g[i] = new int[p[i]];
        for (int i = 0; i < from.length; i++) {
            g[from[i]][--p[from[i]]] = to[i];
            g[to[i]][--p[to[i]]] = from[i];
        }
        return g;
    }
    
    void run() throws Exception
    {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        out = new PrintWriter(System.out);
        
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
    }
    
    public static void main(String[] args) throws Exception { new D().run(); }
    
    private byte[] inbuf = new byte[1024];
    private int lenbuf = 0, ptrbuf = 0;
    
    private int readByte()
    {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }
    
    private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
    
    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }
    
    private String ns()
    {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    
    private char[] ns(int n)
    {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }
    
    private char[][] nm(int n, int m)
    {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }
    
    private int[] na(int n)
    {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }
    
    private int ni()
    {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private long nl()
    {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

Problem solution in C++.

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define foreach(i,x) for(type(x)i = x.begin(); i != x.end(); i++)
#define FOR(ii, aa, bb) for(int ii = aa; ii <= bb; ii++)
#define type(x) __typeof(x.begin())

typedef long long ll;

const int mod = (int) 1e9 + 7;
const int N = 2e5 + 5;

int n, m, x, y, dp[N][11][11], temp[N][11][11];
vector<int> v[N];

void dfs(int node, int root) {
    dp[node][0][0] = 1;
    foreach(it, v[node]) {
        if(*it == root) continue;
        dfs(*it, node);
        FOR(i, 0, 10){
            FOR(j, 0, 10) {
                temp[node][i][j] = dp[node][i][j];
                dp[node][i][j] = 0;
            }
        }
        FOR(i, 0, m){
            FOR(j, 0, m - i){
                FOR(k, 0, m){
                    dp[node][i + j][k] = (dp[node][i + j][k] + temp[node][i][k] * (ll) dp[*it][j][0]) % mod;
                    dp[node][i + j][k + 1] = (dp[node][i + j][k + 1] + temp[node][i][k] * (ll) dp[*it][j][1]) % mod;
                    if(k) dp[node][i + j + 1][k - 1] = (dp[node][i + j + 1][k - 1] + temp[node][i][k] * (ll) dp[*it][j][1] % mod * k) % mod;
                    dp[node][i + j + 1][k] = (dp[node][i + j + 1][k] + temp[node][i][k] * (ll) dp[*it][j][1] % mod) % mod;
                }
            }
        }
    }   
    FOR(i, 0, m) dp[node][i][1] = (dp[node][i][1] + dp[node][i][0]) % mod;
}

int main() {
    cin >> n >> m;
    FOR(i, 2, n) {
        cin >> x >> y;
        v[x].pb(y);
        v[y].pb(x);
    }
    dfs(1, 0);
    cout << dp[1][m][0] << endl;
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _node{
  int x;
  int w;
  struct _node *next;
} lnode;
#define MOD 1000000007
void insert_edge(int x,int y,int w);
void dfs(int x);
int M,trace[100000]={0};
long long dp[6][6][100000]={0};
lnode *table[100000]={0};

int main(){
  int N,x,y,i;
  long long ans;
  scanf("%d%d",&N,&M);
  for(i=0;i<N-1;i++){
    scanf("%d%d",&x,&y);
    insert_edge(x-1,y-1,1);
  }
  dfs(0);
  for(i=ans=0;i<=M;i++)
    ans=(ans+dp[i][M][0])%MOD;
  printf("%lld",ans);
  return 0;
}
void insert_edge(int x,int y,int w){
  lnode *t=malloc(sizeof(lnode));
  t->x=y;
  t->w=w;
  t->next=table[x];
  table[x]=t;
  t=malloc(sizeof(lnode));
  t->x=x;
  t->w=w;
  t->next=table[y];
  table[y]=t;
  return;
}
void dfs(int x){
  int i,j,k,l;
  long long t[6][6];
  lnode *p;
  trace[x]=1;
  dp[0][0][x]=1;
  for(p=table[x];p;p=p->next)
    if(!trace[p->x]){
      dfs(p->x);
      memset(t,0,sizeof(t));
      for(i=0;i<=M;i++)
        for(j=0;i+j<=M+1;j++)
          for(k=0;k<=i;k++)
            for(l=0;l<=j;l++){
              if(i+j<=M){
                t[k][i+j]=(t[k][i+j]+dp[k][i][x]*dp[l][j][p->x])%MOD;
                if(k)
                  t[k-1][i+j]=(t[k-1][i+j]+dp[k][i][x]*dp[l][j][p->x]%MOD*k)%MOD;
                if(k+1<=i+j)
                  t[k+1][i+j]=(t[k+1][i+j]+dp[k][i][x]*dp[l][j][p->x]%MOD*l)%MOD;
              }
              if(i+j && k)
                t[k-1][i+j-1]=(t[k-1][i+j-1]+dp[k][i][x]*dp[l][j][p->x]%MOD*k*l)%MOD;
              if(i+j+1<=M)
                t[k+1][i+j+1]=(t[k+1][i+j+1]+dp[k][i][x]*dp[l][j][p->x])%MOD;
            }
      for(i=0;i<=M;i++)
        for(j=0;j<=M;j++)
          dp[i][j][x]=t[i][j]%MOD;
    }
  return;
}