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.util.ArrayList;importjava.io.*;importjava.util.*;importjava.text.*;importjava.math.*;importjava.util.regex.*;importjava.util.ArrayList;importjava.util.Scanner;enumColor{RED,GREEN}abstractclassTree{privateintvalue;privateColorcolor;privateintdepth;publicTree(intvalue,Colorcolor,intdepth){this.value=value;this.color=color;this.depth=depth;}publicintgetValue(){returnvalue;}publicColorgetColor(){returncolor;}publicintgetDepth(){returndepth;}publicabstractvoidaccept(TreeVisvisitor);}classTreeNodeextendsTree{privateArrayList<Tree>children=newArrayList<>();publicTreeNode(intvalue,Colorcolor,intdepth){super(value,color,depth);}publicvoidaccept(TreeVisvisitor){visitor.visitNode(this);for(Treechild:children){child.accept(visitor);}}publicvoidaddChild(Treechild){children.add(child);}}classTreeLeafextendsTree{publicTreeLeaf(intvalue,Colorcolor,intdepth){super(value,color,depth);}publicvoidaccept(TreeVisvisitor){visitor.visitLeaf(this);}}abstractclassTreeVis{publicabstractintgetResult();publicabstractvoidvisitNode(TreeNodenode);publicabstractvoidvisitLeaf(TreeLeafleaf);}classSumInLeavesVisitorextendsTreeVis{intresult=0;publicintgetResult(){returnresult;}publicvoidvisitNode(TreeNodenode){}publicvoidvisitLeaf(TreeLeafleaf){result+=leaf.getValue();}}classProductOfRedNodesVisitorextendsTreeVis{longresult=1L;publicintgetResult(){return(int)result;}publicvoidvisitNode(TreeNodenode){if(node.getColor()==Color.RED){result=(result*node.getValue())%(1000000007);}}publicvoidvisitLeaf(TreeLeafleaf){if(leaf.getColor()==Color.RED){result=(result*leaf.getValue())%(1000000007);}}}classFancyVisitorextendsTreeVis{intsumOfNode=0;intsumOfLeaf=0;publicintgetResult(){returnMath.abs(sumOfNode-sumOfLeaf);}publicvoidvisitNode(TreeNodenode){if(node.getDepth()%2==0){sumOfNode+=node.getValue();}}publicvoidvisitLeaf(TreeLeafleaf){if(leaf.getColor()==Color.GREEN){sumOfLeaf+=leaf.getValue();}}}publicclassSolution{publicstaticTreesolve(){// read the tree from STDIN and return its root as a return value of this// functionScannersc=newScanner(System.in);intn=sc.nextInt();int[]vals=newint[n];for(inti=0;i<n;i++){vals[i]=sc.nextInt();}Color[]colors=newColor[n];for(inti=0;i<n;i++){colors[i]=sc.nextInt()==1?Color.GREEN:Color.RED;}Map<Integer,Set<Integer>>nodeEdges=newHashMap<>();for(inti=0;i<n-1;i++){intu=sc.nextInt();intv=sc.nextInt();if(!nodeEdges.containsKey(u)){nodeEdges.put(u,newHashSet<Integer>());}if(!nodeEdges.containsKey(v)){nodeEdges.put(v,newHashSet<Integer>());}nodeEdges.get(u).add(v);nodeEdges.get(v).add(u);}Map<TreeNode,Integer>nodeIndexMap=newHashMap<>();List<TreeNode>parents=newArrayList<>();TreeNoderoot=newTreeNode(vals[0],colors[0],0);nodeIndexMap.put(root,1);parents.add(root);while(!parents.isEmpty()){List<TreeNode>nextLevelParents=newArrayList<>();for(TreeNodenode:parents){intdepth=node.getDepth();intparentIndex=nodeIndexMap.get(node);for(intchildIndex:nodeEdges.get(parentIndex)){nodeEdges.get(childIndex).remove(parentIndex);if(!nodeEdges.get(childIndex).isEmpty()){TreeNodechild=newTreeNode(vals[childIndex-1],colors[childIndex-1],depth+1);nextLevelParents.add(child);nodeIndexMap.put(child,childIndex);node.addChild(child);}else{TreeLeafleaf=newTreeLeaf(vals[childIndex-1],colors[childIndex-1],depth+1);node.addChild(leaf);}}}parents=nextLevelParents;}sc.close();returnroot;}publicstaticvoidmain(String[]args){Treeroot=solve();SumInLeavesVisitorvis1=newSumInLeavesVisitor();ProductOfRedNodesVisitorvis2=newProductOfRedNodesVisitor();FancyVisitorvis3=newFancyVisitor();root.accept(vis1);root.accept(vis2);root.accept(vis3);intres1=vis1.getResult();intres2=vis2.getResult();intres3=vis3.getResult();System.out.println(res1);System.out.println(res2);System.out.println(res3);}}
Let's break down the solution step by step:
Visitor Classes
The code defines three visitor classes that extend the abstract class TreeVis. Each visitor implements specific logic for traversing and processing nodes and leaves of the tree.
SumInLeavesVisitor:
Calculates the sum of values in leaf nodes.
Inherits from TreeVis.
Contains an instance variable result to store the sum.
Implements getResult() to return the calculated sum.
Overrides visitNode(TreeNode node) with an empty implementation because this visitor does not operate on internal nodes.
Overrides visitLeaf(TreeLeaf leaf) to add the value of the leaf node to the sum.
ProductOfRedNodesVisitor:
Calculates the product of values in red nodes modulo (10^9 + 7).
Inherits from TreeVis.
Contains an instance variable result to store the product.
Implements getResult() to return the calculated product.
Overrides visitNode(TreeNode node) to check if the node is red and update the product accordingly.
Overrides visitLeaf(TreeLeaf leaf) to check if the leaf is red and update the product accordingly.
FancyVisitor:
Calculates the absolute difference between the sum of values in even-depth nodes and the sum of values in green leaf nodes.
Inherits from TreeVis.
Contains instance variables sumOfNode and sumOfLeaf to store the sums.
Implements getResult() to return the absolute difference between sumOfNode and sumOfLeaf.
Overrides visitNode(TreeNode node) to check if the node depth is even and update sumOfNode.
Overrides visitLeaf(TreeLeaf leaf) to check if the leaf is green and update sumOfLeaf.
solve Method
The solve method is responsible for constructing the tree based on input data obtained from standard input (STDIN). Here's a breakdown of this method:
Read Input:
Creates a Scanner object to read input.
Reads an integer n representing the number of nodes in the tree.
Initializes arrays vals and colors to store node values and colors, respectively.
Populate vals and colors Arrays:
Reads n integers into the vals array, representing node values.
Reads n integers (0 or 1) into the colors array and converts them to Color.RED or Color.GREEN.
Build Node Edges:
Constructs a map nodeEdges to store the edges between nodes.
Reads n - 1 pairs of integers u and v representing edges between nodes u and v.
Populates nodeEdges accordingly.
Construct Tree:
Initializes a map nodeIndexMap to store node indices.
Initializes a list parents to track parent nodes.
Creates the root node (TreeNode) using the first value and color from vals and colors.
Adds the root node to parents and sets its index in nodeIndexMap.
Loops until parents is empty:
Initializes nextLevelParents list for the next level of nodes.
Iterates over each parent node in parents:
Retrieves its depth and index from nodeIndexMap.
For each child index in nodeEdges corresponding to the parent index:
Removes the parent-child edge from nodeEdges.
If the child index has remaining edges (i.e., not a leaf node):
Creates a new TreeNode or TreeLeaf based on the child index, value, color, and depth.
Adds the child to the parent node and updates nodeIndexMap.
Adds the child to nextLevelParents.
Otherwise, creates a TreeLeaf and adds it to the parent node.
Updates parents with the nextLevelParents list.
Return Root:
Closes the Scanner.
Returns the root of the constructed tree.
In summary, the solve method parses input data to build a tree structure with nodes and edges, ensuring correct parent-child relationships. It constructs internal nodes (TreeNode) and leaf nodes (TreeLeaf) based on the input indices, values, colors, and edges. Finally, it returns the root of the constructed tree.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Java Visitor Pattern
You are viewing a single comment's thread. Return to all comments →
Solution:
Let's break down the solution step by step:
Visitor Classes
The code defines three visitor classes that extend the abstract class
TreeVis
. Each visitor implements specific logic for traversing and processing nodes and leaves of the tree.SumInLeavesVisitor
:TreeVis
.result
to store the sum.getResult()
to return the calculated sum.visitNode(TreeNode node)
with an empty implementation because this visitor does not operate on internal nodes.visitLeaf(TreeLeaf leaf)
to add the value of the leaf node to the sum.ProductOfRedNodesVisitor
:TreeVis
.result
to store the product.getResult()
to return the calculated product.visitNode(TreeNode node)
to check if the node is red and update the product accordingly.visitLeaf(TreeLeaf leaf)
to check if the leaf is red and update the product accordingly.FancyVisitor
:TreeVis
.sumOfNode
andsumOfLeaf
to store the sums.getResult()
to return the absolute difference betweensumOfNode
andsumOfLeaf
.visitNode(TreeNode node)
to check if the node depth is even and updatesumOfNode
.visitLeaf(TreeLeaf leaf)
to check if the leaf is green and updatesumOfLeaf
.solve
MethodThe
solve
method is responsible for constructing the tree based on input data obtained from standard input (STDIN). Here's a breakdown of this method:Read Input:
Scanner
object to read input.n
representing the number of nodes in the tree.vals
andcolors
to store node values and colors, respectively.Populate
vals
andcolors
Arrays:n
integers into thevals
array, representing node values.n
integers (0 or 1) into thecolors
array and converts them toColor.RED
orColor.GREEN
.Build Node Edges:
nodeEdges
to store the edges between nodes.n - 1
pairs of integersu
andv
representing edges between nodesu
andv
.nodeEdges
accordingly.Construct Tree:
nodeIndexMap
to store node indices.parents
to track parent nodes.TreeNode
) using the first value and color fromvals
andcolors
.parents
and sets its index innodeIndexMap
.parents
is empty:nextLevelParents
list for the next level of nodes.parents
:nodeIndexMap
.nodeEdges
corresponding to the parent index:nodeEdges
.TreeNode
orTreeLeaf
based on the child index, value, color, and depth.nodeIndexMap
.nextLevelParents
.TreeLeaf
and adds it to the parent node.parents
with thenextLevelParents
list.Return Root:
Scanner
.In summary, the
solve
method parses input data to build a tree structure with nodes and edges, ensuring correct parent-child relationships. It constructs internal nodes (TreeNode
) and leaf nodes (TreeLeaf
) based on the input indices, values, colors, and edges. Finally, it returns the root of the constructed tree.