Kingdom Division – ASOCIATIA „INVESTESTE PENTRU VIITORUL TAU” BUZAU

Cerinta completa

King Arthur has a large kingdom that can be represented as a tree, where nodes correspond to cities and edges correspond to the roads between cities. The kingdom has a total of cities numbered from to .

The King wants to divide his kingdom between his two children, Reggie and Betty, by giving each of them or more cities; however, they don’t get along so he must divide the kingdom in such a way that they will not invade each other’s cities. The first sibling will invade the second sibling’s city if the second sibling has no other cities directly connected to it. For example, consider the kingdom configurations below:

Given a map of the kingdom’s cities, find and print the number of ways King Arthur can divide it between his two children such that they will not invade each other. As this answer can be quite large, it must be modulo .

Input Format

The first line contains a single integer denoting (the number of cities in the kingdom).
Each of the subsequent lines contains two space-separated integers, and , describing a road connecting cities and .

Constraints

It is guaranteed that all cities are connected.

Subtasks

for of the maximum score.

Output Format

Print the number of ways to divide the kingdom such that the siblings will not invade each other, modulo .

Sample Input

Sample Output

Explanation

In the diagrams below, red cities are ruled by Betty and blue cities are ruled by Reggie. The diagram below shows a division of the kingdom that results in war between the siblings:

Because cities and are not connected to any other red cities, blue city will cut off their supplies and declare war on them. That said, there are four valid ways to divide the kingdom peacefully:

We then print the value of as our answer.

Limbajul de programare folosit: java8

Cod:

import java.io.*;
import java.util.*;

public class Solution {
    static final long MOD = 1_000_000_007L;

    private static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { this.in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c;
            do { c = read(); } while (c <= ' ' && c != -1);
            int sign = 1;
            if (c == '-') { sign = -1; c = read(); }
            int val = 0;
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = read();
            }
            return val * sign;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();

        @SuppressWarnings("unchecked")
        ArrayList<Integer>[] g = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) g[i] = new ArrayList<>();

        for (int i = 0; i < n - 1; i++) {
            int u = fs.nextInt();
            int v = fs.nextInt();
            g[u].add(v);
            g[v].add(u);
        }

        int[] parent = new int[n + 1];
        int[] order = new int[n];
        int ord = 0;

        int[] stack = new int[n];
        int top = 0;
        stack[top++] = 1;
        parent[1] = -1;

        while (top > 0) {
            int u = stack[--top];
            order[ord++] = u;
            for (int v : g[u]) {
                if (v == parent[u]) continue;
                parent[v] = u;
                stack[top++] = v;
            }
        }

        long[] same = new long[n + 1]; // color(u) == color(parent)
        long[] diff = new long[n + 1]; // color(u) != color(parent)

        for (int idx = n - 1; idx >= 0; idx--) {
            int u = order[idx];
            long total = 1;
            long allDiff = 1;

            for (int v : g[u]) {
                if (v == parent[u]) continue;
                long waysSame = same[v];
                long waysDiff = diff[v];
                total = (total * ((waysSame + waysDiff) % MOD)) % MOD;
                allDiff = (allDiff * waysDiff) % MOD;
            }

            same[u] = total;
            diff[u] = (total - allDiff + MOD) % MOD;
        }

        long ans = (2L * diff[1]) % MOD;
        System.out.println(ans);
    }
}

Scor obtinut: 1.0

Submission ID: 464617758

Link challenge: https://www.hackerrank.com/challenges/kingdom-division/problem

Kingdom Division