fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3. import java.text.*;
  4. import java.math.*;
  5. import java.util.regex.*;
  6. class implemento {
  7.     static int n;
  8.     static int k;
  9.     static ArrayList<Integer> child[];
  10.     static long default_[][];
  11.     public static void main(String[] args)throws IOException {
  12.             BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  13.             String p[]=br.readLine().split(" ");
  14.             n=Integer.parseInt(p[0]);
  15.             k=Integer.parseInt(p[1]);
  16.             //stores the adjacency list for the tree
  17.             ArrayList<Integer> adjacency[]=new ArrayList[n];
  18.  
  19.             for(int i=0;i<n;i++) adjacency[i]=new ArrayList<Integer>();
  20.             //reading edges (w,v) for the input tree
  21.             for(int i=1;i<n;i++){
  22.                 String p1[]=br.readLine().split(" ");
  23.                 int v=Integer.parseInt(p1[0])-1;
  24.                 int w=Integer.parseInt(p1[1])-1;
  25.                 adjacency[v].add(w);
  26.                 adjacency[w].add(v);
  27.             }
  28.             //lines 29 through initialize the given tree as a linked data structure
  29.             Stack<Integer> temp=new Stack<Integer>();
  30.             temp.push(0);
  31.             boolean trav[]=new boolean[n];
  32.             trav[0]=true;
  33.             child=new ArrayList[n];
  34.             for(int i=0;i<n;i++){
  35.                 child[i]=new ArrayList<Integer>();
  36.             }
  37.             int parent[]=new int[n];
  38.             parent[0]=-1;
  39.             while(temp.size()>0){
  40.                     int x=temp.peek();
  41.                     int l2=adjacency[x].size();boolean change =false;
  42.                     for(int u=0;u<l2;u++){
  43.                         int v=adjacency[x].get(u);
  44.                         if(!trav[v]){
  45.                             parent[v]=x;
  46.                             temp.push(v);
  47.                             change=true;
  48.                             trav[v]=true;
  49.                             break;
  50.                             }
  51.                     }
  52.                     if(!change){temp.pop();}
  53.             }
  54.              for(int i=0;i<n;i++){
  55.                 if(parent[i]>=0){
  56.                       child[parent[i]].add(i);}
  57.             }
  58.             GenericTreeNode root=initialize(0);
  59.             default_=new long[2][k+1];
  60.             default_[0][0]=1;
  61.             default_[1][0]=1;
  62.             long a[][]=getSubtreeInclude_Exclude(root);
  63.             //a[0] is the exclude array
  64.             //a[1] is the include array
  65.             long sum=0;
  66.                 for(int i=0;i<=k;i++){
  67.                     sum+=a[0][i]+a[1][i];
  68.              }
  69.                 System.out.println(sum);
  70.                 for(int i=0;i<2;i++){
  71.                     for(int j=0;j<=k;j++)
  72.                         System.out.print(a[i][j]+"  ");
  73.                     System.out.println();
  74.  
  75.                 }
  76.            }
  77.            //function to initialise the given tree
  78.     static GenericTreeNode initialize(int root){
  79.        if(child[root].size()==0){
  80.         return new GenericTreeNode(root);
  81.         }
  82.         else{int l=child[root].size();
  83.             GenericTreeNode temp=new GenericTreeNode(root);
  84.             for(int i=0;i<l;i++){
  85.                 GenericTreeNode t=initialize(child[root].get(i));
  86.                 temp.children.add(t);
  87.             }
  88.             return temp;
  89.         }
  90.     }
  91.     // display the given tree
  92.     static void display(GenericTreeNode root){
  93.         System.out.println(root.node);
  94.         if(!(root.children.size()==0||root.children==null))
  95.         {
  96.             int l=root.children.size();
  97.             for(int i=0;i<l;i++){
  98.                 display(root.children.get(i));
  99.             }
  100.         }
  101.     }
  102.     //finds the number of valid subtrees
  103.     static long[][] getSubtreeInclude_Exclude(GenericTreeNode root){
  104.         if(root.children.size()==0||root.children==null) {
  105.             //base case when tree is just a node with no children
  106.             //return include as[1,0,0,0...]
  107.             //return exclude as[1,0,0,0...]
  108.              return default_;
  109.             }
  110.         else{
  111.              GenericTreeNode L=root.children.get(0);
  112.              root.children.remove(L);
  113.              long l[][]=getSubtreeInclude_Exclude(L);
  114.              long r[][]=getSubtreeInclude_Exclude(root);
  115.              long tvInclude[]=new long[k+1];
  116.              long tvExclude[]=new long[k+1];
  117.              tvExclude[0]=1;
  118.              tvInclude[0]=1;
  119.             for(int i=1;i<=k;i++){
  120.                 tvExclude[i]=l[0][i]+r[1][i-1]+r[0][i];
  121.             }
  122.             for(int i=1;i<=k;i++){
  123.                 long sum=0;
  124.                 for(int j=0;j<=i;j++){
  125.                     int k1=i-j;
  126.                     sum+=(l[1][j]*r[1][k1]);
  127.                 }
  128.                 tvInclude[i]=l[1][i-1]+sum;
  129.             }
  130.             long ret[][]=new long[2][k+1];
  131.             ret[0]=tvExclude;
  132.             ret[1]=tvInclude;
  133.             //return the include/exclude arrays for this step
  134.             return ret;
  135.         }
  136.     }
  137.     }
  138. class GenericTreeNode{
  139.     int node;
  140.     ArrayList<GenericTreeNode> children;
  141.     GenericTreeNode(){
  142.         children=new ArrayList<GenericTreeNode>();
  143.         node=0;
  144.     }
  145.     GenericTreeNode(int n){
  146.         children=new ArrayList<GenericTreeNode>();
  147.         node=n;
  148.        }
  149.  
  150. }
  151.  
Success #stdin #stdout 0.08s 381184KB
comments (?)
stdin
copy 
4 4
1 2
1 3
1 4
stdout
copy 
11
1  3  3  0  0  
1  3  0  0  0
https://ideone.com/gVPBcz
language:
Java (HotSpot 12)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!