Shulou(Shulou.com)06/03 Report--

This article mainly shows you "how Java realizes General G of Bluebridge Cup". The content is easy to understand and clear. I hope it can help you solve your doubts. Let me lead you to study and learn this article "how to realize General G of Bluebridge Cup by Java".

General G has a well-trained army in which every soldier except General G has a direct superior (either other soldiers or General G). Now General G will take on a special task and need to send some soldiers (at least one) to form an death squad. In order to increase the independence of the members, it is required that if a soldier is in the team, his direct superiors cannot be in the team. Excuse me, how many methods does General G have to dispatch teams? Note that General G can also join the team as a soldier. The first line of the input format contains an integer n that represents the number of troops, including General G. The soldiers of the army are numbered from 1 to n, and General G is numbered 1. Next, there is a number of nmurs, which means the numbers are 2, 3, … The direct superior number of the soldier n, and the direct superior number of the soldier numbered I is less than I. The output format outputs an integer that represents the number of scenarios for the dispatch team. Since the number may be large, you only need to output the remainder of this number divided by 10007. Sample input 131 sample output 14 examples show that the four methods are:

Choose 1; choose 2; choose 3; choose 2, 3. Sample input 271 1 2 2 3 3 sample output 240data size and convention for 20% data, n ≤ 20; for 40% data, n ≤ 100; for 100% data, 1 ≤ n ≤ 100000.

Resource convention: peak memory consumption (including virtual machines) < 256MCPU consumption < 2000ms

Please output strictly according to the requirements, do not superfluously print something like: "Please enter …" Superfluous content.

All the code is placed in the same source file, and after debugging is passed, copy and submit the source code. Note: do not use the package statement. Do not use features of jdk1.7 or above. Note: the name of the main class must be: Main, otherwise it will be handled as invalid code.

Import java.util.ArrayList;import java.util.Scanner;public class Main {public static int n; public static int MOD = 10007; public static ArrayList [] list; public static long [] [] dp; public void dfs (int root) {dp [root] [0] = 1; dp [root] [1] = 1; for (int I = 0 root I < list [root] .size (); iSize +) {int child = list [root] .get (I); dfs (child) Dp [root] [0] = dp [root] [0] * (dp [child] [0] + dp [child] [1])% MOD; dp [root] [1] = dp [root] [1] * dp [child] [0]% MOD;}} @ SuppressWarnings ("unchecked") public static void main (String [] args) {Main test = new Main (); Scanner in = new Scanner (System.in); n = in.nextInt () List = new ArrayList [n + 1]; for (int I = 1 + I)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.