import java.io.PrintStream; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Queue; import java.util.Scanner; /** * Solution to Red Black Tree * * @author vanb */ public class redblack_vanb { private static Scanner sc; private static PrintStream ps; private static final long MOD = 1000000007; /** * A Node of the Red Black Tree * * @author vanb */ private class Node { /** Is this a Red node? */ public boolean isred = false; /** Children of this node */ public List children = new ArrayList(); /** * counts[i] is the number of ways of choosing subsets with i red nodes * in the subtree rooted at this node. */ public long counts[] = null; /** The maximum number of red nodes choosable in this subtree */ public int max = 0; /** This is for a DFS just for the judges to confirm that the input forms a tree. */ public boolean visited = false; /** * Visit this node in a DFS to confirm that the input is a tree. */ public void visit() { if( visited ) System.err.println( "PANIC!! It's not a tree! There is a cycle! " ); else { visited = true; for( Node child : children ) child.visit(); } } /** * Compute the counts[] array (where counts[i] is the number of ways * of choosing (non-empty) subsets with i red nodes in the subtree rooted at this node) * using the children of this node. */ public void countSets() { // Is this a leaf? if( children.size()==0 ) { if( isred ) { // Red leaf max = 1; counts = new long[]{ 0L, 1L }; } else { // Black leaf max = 0; counts = new long[]{ 1L }; } } else { // Computing the max # of red nodes for this node // will help us keep the arrays as small as possible for( Node child : children ) { // Comment the next line out if using the non-recursive version. child.countSets(); max += child.max; } long oldcounts[] = new long[max+1]; long newcounts[] = new long[max+1]; Arrays.fill( newcounts, 0L ); // How many red nodes have we seen so far? int sofar = 0; for( Node child : children ) { // Build the newcounts on the oldcounts. // We've got to make a copy so that the process doesn't // corrupt newcounts. System.arraycopy( newcounts, 0, oldcounts, 0, max+1 ); // Count subsets from children for( int j=0; j<=child.max; j++ ) { // How many ways can we put this child's subsets // together with the subsets of children we've already handled? for( int i=0; i<=sofar; i++ ) { newcounts[i+j] += oldcounts[i]*child.counts[j]; newcounts[i+j] %= MOD; } // How many subsets can we get with this child alone, // not combining it with other children? newcounts[j] += child.counts[j]; newcounts[j] %= MOD; } sofar += child.max; } counts = newcounts; // Account for this node itself. If we use this // node, we can't use any of the nodes in its children's subtrees, // since they would be ancestors. // So this gives us just one more subset, // in counts[1] if it's red, or counts[0] if it's black. if( isred ) { if( counts.length<2 ) { // Special case: What if this is the first red node we've seen? counts = new long[]{ counts[0], 1 }; max = 1; } else { ++counts[1]; counts[1] %= MOD; } } else { ++counts[0]; counts[0] %= MOD; } children.clear(); } } } /** * Do it! */ private void doit() { int n = sc.nextInt(); int k = sc.nextInt(); // Create n nodes Node nodes[] = new Node[n]; for( int i=0; i queue = new ArrayDeque(n); // ArrayDeque stack = new ArrayDeque(n); // queue.add( nodes[0] ); // while( !queue.isEmpty() ) // { // Node node = queue.poll(); // stack.addFirst( node ); // queue.addAll( node.children ); // } // OK, they're in order, so count the sets. // while( !stack.isEmpty() ) stack.poll().countSets(); // Confirm that the input is a tree. // This will be done locally, and can be commented out. nodes[0].visit(); for( Node node : nodes ) if( !node.visited ) System.err.println( "PANIC!! 1 isn't the root."); // OK, it's a tree, now count the sets. nodes[0].countSets(); // Get the answers long answers[] = nodes[0].counts; // Account for the null set ++answers[0]; // Print the answers for( int i=0; i<=k; i++ ) { ps.println( i