We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
importjava.io.*;importjava.math.*;importjava.text.*;importjava.util.*;importjava.util.regex.*;publicclassSolution{privateMap<Integer,List<Integer>>roads=newHashMap<>();/* * Complete the repairRoads function below. */staticintrepairRoads(intn,int[][]roads){/* * Write your code here. */Solutionsolution=newSolution();for(inti=0;i<n-1;i++){System.out.println(roads[i][0]+"-"+roads[i][1]);solution.addRoad(roads[i][0],roads[i][1]);}returnsolution.solve();}privatestaticfinalScannerscanner=newScanner(System.in);publicstaticvoidmain(String[]args)throwsIOException{BufferedWriterbufferedWriter=newBufferedWriter(newFileWriter(System.getenv("OUTPUT_PATH")));intt=Integer.parseInt(scanner.nextLine().trim());for(inttItr=0;tItr<t;tItr++){intn=Integer.parseInt(scanner.nextLine().trim());int[][]roads=newint[n-1][2];for(introadsRowItr=0;roadsRowItr<n-1;roadsRowItr++){String[]roadsRowItems=scanner.nextLine().split(" ");for(introadsColumnItr=0;roadsColumnItr<2;roadsColumnItr++){introadsItem=Integer.parseInt(roadsRowItems[roadsColumnItr].trim());roads[roadsRowItr][roadsColumnItr]=roadsItem;}}intresult=repairRoads(n,roads);bufferedWriter.write(String.valueOf(result));bufferedWriter.newLine();}bufferedWriter.close();}privatevoidaddToTree(RoadTreeroadTree,intlevel,Integercity,Integerparent){List<Integer>roadsFromCity=roads.get(city);if(parent!=null){roadsFromCity.remove(parent);}roadTree.add(city,roadsFromCity,level+1);for(Integerc:roadsFromCity){addToTree(roadTree,level+1,c,city);}}publicintsolve(){intresult=0;intlevel=0;RoadTreeroadTree=newRoadTree(roads.size());Integerroot=roads.keySet().iterator().next();addToTree(roadTree,level,root,null);for(inti=roadTree.levels.lastKey()-1;i>0;i--){List<Integer>cities=roadTree.levels.get(i);for(Integercity:cities){List<Integer>leaves=roadTree.roads.get(city);if(leaves!=null&&leaves.isEmpty()==false){for(Integerinteger:leaves){roadTree.points[city]+=roadTree.points[integer];}if(roadTree.points[city]==0){roadTree.points[city]++;}elseif(roadTree.points[city]%2==0){result+=roadTree.points[city]/2;roadTree.points[city]=0;}for(Integerinteger:leaves){roadTree.roads.remove(integer);}if(roadTree.points[city]==0){roadTree.remove(city);}}}}returnresult+(roadTree.points[root]+1)/2;}publicstaticclassRoadTree{privateint[]parents;privateMap<Integer,List<Integer>>roads=newHashMap<>();privateTreeMap<Integer,List<Integer>>levels=newTreeMap<>();privateint[]points;publicRoadTree(intnumberOfCities){points=newint[numberOfCities];parents=newint[numberOfCities];}publicvoidadd(Integercity,List<Integer>roads,Integerlevel){if(levels.containsKey(level)==false){levels.put(level,newArrayList<Integer>());}this.roads.put(city,roads);levels.get(level).add(city);for(Integerinteger:roads){parents[integer]=city;}}publicvoidremove(Integercity){roads.get(parents[city]).remove(city);roads.remove(city);}}publicvoidaddRoad(intcity1,intcity2){addConnection(city1,city2);addConnection(city2,city1);}privatevoidaddConnection(intcity1,intcity2){if(roads.containsKey(city1)){roads.get(city1).add(city2);}else{List<Integer>cities=newArrayList<>();cities.add(city2);roads.put(city1,cities);}}}
Repair Roads
You are viewing a single comment's thread. Return to all comments →