import java.io.*; import java.util.*; public class uniformsubtree_topraj_sortedints { final static int DEBUG = 0; final static int MAX = 1000000; Scanner sc; PrintWriter pw; HashMap id_to_nextid[] = new HashMap[5500]; Rep reps[] = new Rep[MAX]; int total = 1; int id_count[] = new int[MAX]; int ids[] = new int[MAX]; int ids_total = 0; class Rep { int curr_num; Rep next; public Rep(int _curr_num, Rep _next) { curr_num = _curr_num; next = _next; } } char tree_rep_cs[]; int ID = 0; class Node { ArrayList children; ArrayList uniform_subtrees; public Node() { children = new ArrayList(); uniform_subtrees = new ArrayList(); } } Node parseTree(int si, int ei) { Node node = new Node(); if(si+1==ei) return node;//leaf si++; ei--; int starti = si; int counter = 0; for(int i=si;i<=ei;i++) { if(tree_rep_cs[i]=='(') counter++; if(tree_rep_cs[i]==')') counter--; if(counter==0) { node.children.add(parseTree(starti, i)); starti = i+1; } } return node; } String getTreeRep(Node node) { String rStr = "("; for(int i=0;i getRepList(int id) { ArrayList list = new ArrayList(); Rep rep = reps[id]; do { list.add(rep.curr_num); rep = rep.next; } while(rep!=null); return list; } void sortIt(Node node) { Collections.sort(node.uniform_subtrees); } public void doIt() throws Exception { sc = new Scanner(new File("uniformsubtree.in")); pw = new PrintWriter(new FileOutputStream("uniformsubtree_topraj.out")); for(int i=0;i(); } reps[0] = null;//the empty string id_to_nextid[0].put(0, 1); reps[1] = new Rep(0, null); total++; for(int test_num=0;;test_num++) { String tree_rep = sc.next(); if(tree_rep.equals("0")) break; tree_rep_cs = tree_rep.toCharArray(); Node root = parseTree(0, tree_rep_cs.length-1); if(DEBUG>0) { String rep = getTreeRep(root); if(!rep.equals(tree_rep)) { System.out.printf("Tree is parsed incorrectly\n"); System.exit(-1); } } solveIt(root); // System.out.printf("done with test: %d\n", test_num); // System.out.printf("total entries = %d\n", root.uniform_subtrees.size()); // String strs[] = new String[root.uniform_subtrees.size()]; // for(int i=0;i answers[] = new ArrayList[root.uniform_subtrees.size()]; for(int i=0;i list = answers[i]; for(int k=0;k> { public int compare(ArrayList a, ArrayList b) { for(int i=0;i