Drevesa

[lukazlatecan]

Pri svojem raziskovalnem delu se Janez ukvarja z dvojiškimi drevesi. Da bi sodelavcu dokazal svojo superiornost, je skonstruiral dvojiško drevo, ki je protiprimer za sodelavčevo domnevo. Žal pa je protiprimer zapisal na list, ki se je izgubil med stotinami podobnih listov na njegovi pisalni mizi (kot pri večini raziskovalcev, urejenost ni ravno Janezova močna točka). Da bi bilo vse skupaj še hujše, si Janez ni zapisal vseh podatkov o drevesu, ampak je za vsako vozlišče zgolj zabeležil, katero je njegovo nadrejeno vozlišče. Spomni pa se, da je bilo skonstruirano drevo levo poravnano.

Ker je vseh dreves na listih na njegovi pisalni mizi občutno preveč, da bi v nekaj dnevih uspel poiskati pravega, te je prosil za pomoč. Zelo bi mu pomagal že s tem, če bi iz množice podatkov o drevesih izbral le takšne, ki bi lahko predstavljali levo poravnano dvojiško drevo.

Poduk: Levo poravnano dvojiško drevo je polno drevo, ki mu morda manjkajo nekateri listi na desni strani v spodnjem nivoju (glej sliko).



Vhodni podatki
Prva vrstica vhodne datoteke vsebuje eno samo število n, tj. število testnih primerov. V prvi vrstici vsakega primera je število vozlišč dvojiškega drevesa m, nato pa sledi za vsako vozlišče po ena vrstica, ki vsebuje dve števili: [math]a_i in [math]b_i. Število [math]a_i predstavlja enolično oznako vozlišča, število [math]b_i pa oznako njegovega starša. Če je vozlišče [math]a_i koren drevesa, je [math]b_i enak −1. Podatki zagotovo predstavljajo neko dvojiško drevo.

Omejitve vhodnih podatkov

• n ≤ 100
• m ≤ 100000
• 0 ≤ [math]a_i ≤ 100000
• −1 ≤ b ≤ 100000

Izhodni podatki
Za vsak testni primer izpiši po eno številko (vsako v svoji vrstici):

1, če podatki lahko predstavljajo levo poravnano dvojiško drevo in 0 sicer.

Primer vhoda

Koda: Izberi vse

3
3
5 3
3 -1
7 3
3
1 -1
3 1
7 3
9
1 -1
2 1
3 1
4 2
5 2
6 3
7 3
8 4
9 7

Pripadajoč izhod

Koda: Izberi vse

1
0
0

[hinkopihpih]

Koda: Izberi vse

import java.util.*;

class Node
{
   private int key;
   private int index;
   private Node left;
   private Node right;

   public Node(int key, int index, Node left, Node right)
   {
      this.key = key;
      this.index = index;
      this.left = left;
      this.right = right;
   }
   public void setKey(int key)
   {
      this.key = key;
   }
   public int getKey()
   {
      return this.key;
   }
   public void setIndex(int index)
   {
      this.index = index;
   }
   public int getIndex()
   {
      return this.index;
   }
   public void setLeft(Node left)
   {
      this.left = left;
   }
   public Node getLeft()
   {
      return this.left;
   }
   public void setRight(Node right)
   {
      this.right = right;
   }
   public Node getRight()
   {
      return this.right;
   }
}

public class Drevesa
{
   public static void main(String[]args)
   {
      Scanner skan = new Scanner(System.in);
      int n = skan.nextInt();

      for(int i = 0; i < n; i++)
      {
         Node root = new Node(0,1,null,null);
         int m = skan.nextInt();
         List<int[]> connections = new ArrayList<int[]>();

         for(int j = 0; j < m; j++)
         {
            int[] connection = new int[2];
            connection[0] = skan.nextInt();
            connection[1] = skan.nextInt();

            if(connection[1] == -1)
            {
               root.setKey(connection[0]);
               continue;
            }   

            connections.add(connection);
         }   

         create(root,connections);

         if(check(root,1,m))
         {
            System.out.println(1);
         }   
         else
         {
            System.out.println(0);
         }   
      }   
   }
   public static void create(Node root, List<int[]> connections)
   {
      if(connections.size() == 0 || root == null)
      {
         return;
      }   

      for(int i = 0; i < connections.size(); i++)
      {
         if(connections.get(i)[1] == root.getKey())
         {
            if(root.getLeft() == null)
            {
               root.setLeft(new Node(connections.get(i)[0], 2 * root.getIndex(), null, null));
               connections.remove(i);
               i--;
            }
            else
            {
               root.setRight(new Node(connections.get(i)[0], 2 * root.getIndex() + 1, null, null));   
               connections.remove(i);
               i--;
               break;
            }   
         }   
      }

      create(root.getLeft(),connections);
      create(root.getRight(),connections);   
   }
   public static boolean check(Node root, int index, int n)
   {
      if(root == null)
      {
         return true;
      }

      root.setIndex(index);

      if(root.getIndex() > n)
      {
         return false;
      }   

      boolean check1 = check(root.getLeft(),2 * root.getIndex(),n);
      boolean check2 = check(root.getRight(),2 * root.getIndex() + 1,n);
      swap(root);
      boolean check3 = check(root.getLeft(),2 * root.getIndex(),n);
      boolean check4 = check(root.getRight(),2 * root.getIndex() + 1,n);
      swap(root);

      return check1 && check2 || check3 && check4;
   }   
   public static void swap(Node root)
   {
      Node temp = root.getLeft();
      root.setLeft(root.getRight());
      root.setRight(temp);
   }
}