Cerinta completa

Byteland has cities (numbered from to ) and bidirectional roads. A path is comprised of 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 paths on any given workday. He cannot work on the same road twice in one day (so no paths can contain the same roads). Steven can start his workday in any city and, once he has finished maintaining a path, teleport to his next starting city.

Given , help Steven determine how many different possible path sets will allow him to perform his maintenance duties. Then print the answer modulo .

Input Format

The first line contains space-separated integers, (the number of cities) and (the number of roads to maintain).
Each line of the subsequent lines contains space-separated integers, , describing a bidirectional road between cities and .

Constraints

Output Format

Find the number of different path sets that will allow Steven to complete orders, and print the answer .

Sample Input

4 2
1 2
2 3
2 4

Sample Output

6

Explanation

For the following Byteland map:

Steven can maintain roads using any of the following routes:

  1. and
  2. and
  3. and
  4. and
  5. and
  6. and

Thus, we print the result of on a new line, which is .

Limbajul de programare folosit: cpp14

Cod:

#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;
}

Scor obtinut: 1.0

Submission ID: 464647666

Link challenge: https://www.hackerrank.com/challenges/road-maintenance/problem

Road Maintenance