題目描述
物件導向程式設計有一個很重要的開放/封閉原則，就是要能擴充但禁止修改。換句話說，新的功能會是以擴充的方式加在現有的程式之下，而非直接去修改先前寫的程式。這個題目模擬了一個現實中的問題，必須使用物件導向程式設計的開放/封閉原則來實作出來。
有一個「Tree」類別有以下3個public的方法：
- getValue()：回傳節點所儲存的值。
- getColor()：回傳節點的顏色。
- getDepth()：回傳節點的深度。根節點的深度為0。
在這個題目中，我們將樹的內部實作當作是封閉不可修改的，然而在現實世界的情況下，樹應該要可以允與外部的類別來擴充它的功能。具體來說，他允許「TreeVis」類別的物件來使用「accept」方法走訪樹的結構。
題目共有兩大部份。
首先實作出SumInLeavesVisitor、ProductRedNodesVisitor、和FancyVisitor三個不同的訪問者類別(TreeVis)，且每個類別都會有以下3個方法：
- getResult()：回傳一個整數結果。「SumInLeavesVisitor」類別會回傳樹中葉子節點所儲存的值之總和；「ProductRedNodesVisitor」類別會回傳紅色節點所儲存的值之積再除以109+7的餘數，如果沒有找到符合的節點則回傳1；「FancyVisitor」類別則是會回傳深度為偶數的非葉子節點之總和與綠色葉子節點的總和之差的絕對值。
- visitNode(TreeNode node)：訪問樹的非葉子節點。
- visitLeaf(TreeLeaf leaf)：訪問樹的葉子節點。
接著要讀取資料並建立出樹。共有n個，編號i為1到n的節點，xi為節點的數值，ci為節點的顏色。樹的根節點編號為1。
原題網址
輸入格式
第一行是一個整數n，就是樹所擁有節點的數量。第二行有n個整數xi，表示各節點的數值，用空格分隔。第三行有n個整數ci，表示各節點的顏色，用空格分隔，0代表紅色，1代表綠色。接下來還有n-1行的輸入，每行有兩個整數ui和vi，描述兩個節點間的邊。
n的範圍在2到105之間(包含2和105)，xi的範圍在1到103之間(包含1和103)，ci只能是0或是1，ui和vi的範圍在1到n之間(包含1和n)。編號1的節點一定是樹的根節點。
輸出格式
輸出有三行，分別是SumInLeavesVisitor、ProductRedNodesVisitor、和FancyVisitor的「getResult」方法的回傳結果。
範例輸入
4 7 2 5 12
0 1 0 0 1
1 2
1 3
3 4
3 5
範例輸出
40
15
額外解釋
根據輸入，可以畫出如下的樹圖：
0 [1, 4, 紅]
/ \
1 [2, 7, 綠] [3, 2, 紅]
/ \
2 [4, 5, 紅] [5, 12, 綠]
一組中括號為一個節點，其中的3個值分別是[i, xi, ci]。
第一行是「SumInLeavesVisitor」的結果，為所有葉子節點值的總和，也就是：
第二行是「ProductRedNodesVisitor」的結果，為紅色節點所儲存的值之積再除以109+7的餘數，也就是：
第三行是「FancyVisitor」的結果，為深度是偶數的非葉子節點之總和與綠色葉子節點的總和之差的絕對值，也就是：
解題概念
此題最難的地方是建立樹的方式，ui和vi的順序沒有保證前後父子關係，因此會造成資料進來的時候會很混亂。而且節點最多可能會有100000個，如果沒有處理好邊的話，會有明顯效能上的問題。由於在建立樹的節點時就要先決定好這個節點的深度和其子節點，因此這題使用DFS(Depth-first search, 廣度優先搜尋法)來建立樹會比較適當。
首先，在一開始的時候，由於輸入量可能會很大，因此使用Scanner加上BufferedInputStream來讀取標準輸入串流，把節點的各項資料讀至記憶體中儲存。在讀取節點的邊時，可以把輸入進來的每組ui和vi掉換順序再存一份，方便之後計算。舉例來說。如果輸入的資料是「1 5」，有可能1是5的父節點，也有可能5才是1的父節點，要知道他們的父子關係，必須在所有邊都讀取完之後從根節點走訪才能知道，因此我們可以先把這兩種可能都存下來，作為到時走訪時的可用路徑。
接著建立Tree(節點)的陣列，陣列大小為n。再來就可以開始實作遞迴的DFS了。我們可以把剛才讀進來的節點資料和Tree的陣列再加上前一個節點和目前節點的索引值和目前節點的深度作為DFS的輸入。在每次DFS遞迴的時候都要去判斷目前節點是否擁有子節點，如果沒有的話(或只有一個我們透過輸入的邊事先預設的子節點)，表示這個節點是樹的葉節點，需使用「TreeLeaf」類別來建立出物件實體，並存進Tree的陣列中；如果目前節點擁有子節點，需使用「TreeNode」類別來建立出物件實體，並存進Tree的陣列中接著要準備繼續遞迴呼叫DFS函數來走訪子節點。在走訪前需先判斷子節點是否就是前一個節點，如果是的話表示這個路徑方向是錯誤的(因為一開始我們把每個輸入的邊都存成兩種方向)，要跳過該節點，否則會出現循環(cycle)而無窮遞迴。每走訪一個子節點，就使用「addChild」方法將其加入至目前的「TreeNode」物件。全都走訪之後，Tree的陣列中的所有節點物件就都建立好了，索引0的位置即為根節點。
最後依照題目要求實作「SumInLeavesVisitor」、「ProductOfRedNodesVisitor」和「FancyVisitor」類別，這裡比較需要注意的是，由於「ProductOfRedNodesVisitor」的結果是很多數值的乘績，因此會有溢位的情形，可以使用「BigInteger」類別來協助計算乘績，最後再除以「1000000007」並取餘數來轉成整數。
參考答案
import java.io.*;
import java.util.*;
import java.math.*;
import java.util.ArrayList;
import java.util.Scanner;
enum Color {
RED, GREEN
}
abstract class Tree {
private int value;
private Color color;
private int depth;
public Tree(int value, Color color, int depth) {
this.value = value;
this.color = color;
this.depth = depth;
}
public int getValue() {
return value;
}
public Color getColor() {
return color;
}
public int getDepth() {
return depth;
}
public abstract void accept(TreeVis visitor);
}
class TreeNode extends Tree {
private ArrayList<Tree> children = new ArrayList<>();
public TreeNode(int value, Color color, int depth) {
super(value, color, depth);
}
public void accept(TreeVis visitor) {
visitor.visitNode(this);
for (Tree child : children) {
child.accept(visitor);
}
}
public void addChild(Tree child) {
children.add(child);
}
}
class TreeLeaf extends Tree {
public TreeLeaf(int value, Color color, int depth) {
super(value, color, depth);
}
public void accept(TreeVis visitor) {
visitor.visitLeaf(this);
}
}
abstract class TreeVis {
public abstract int getResult();
public abstract void visitNode(TreeNode node);
public abstract void visitLeaf(TreeLeaf leaf);
}
class SumInLeavesVisitor extends TreeVis {
int result = 0;
public int getResult() {
return result;
}
public void visitNode(TreeNode node) {
// do nothing
}
public void visitLeaf(TreeLeaf leaf) {
result += leaf.getValue();
}
}
class ProductOfRedNodesVisitor extends TreeVis {
final BigInteger modInt = BigInteger.valueOf(1000000007);
BigInteger result = BigInteger.ONE;
public int getResult() {
return result.mod(modInt).intValue();
}
public void visitNode(TreeNode node) {
if (node.getColor() == Color.RED) {
result = result.multiply(BigInteger.valueOf(node.getValue()));
}
}
public void visitLeaf(TreeLeaf leaf) {
if (leaf.getColor() == Color.RED) {
result = result.multiply(BigInteger.valueOf(leaf.getValue()));
}
}
}
class FancyVisitor extends TreeVis {
int result = 0;
public int getResult() {
return Math.abs(result);
}
public void visitNode(TreeNode node) {
if (node.getDepth() % 2 == 0) {
result += node.getValue();
}
}
public void visitLeaf(TreeLeaf leaf) {
if (leaf.getColor() == Color.GREEN) {
result -= leaf.getValue();
}
}
}
public class Solution {
public static Tree solve() throws FileNotFoundException {
final Scanner sc = new Scanner(new BufferedInputStream(System.in));
final int n = Integer.valueOf(sc.nextLine());
final HashMap<Integer, Set<Integer>> edgeMap = new HashMap<>();
final Set<Integer>[] childrenSet = new HashSet[n];
for (int i = 0; i < n; ++i) {
edgeMap.put(i, new HashSet());
childrenSet[i] = new HashSet<>();
}
final int[] x = new int[n];
final Color[] c = new Color[n];
for (int i = 0; i < n; ++i) {
x[i] = sc.nextInt();
}
for (int i = 0; i < n; ++i) {
c[i] = sc.nextInt() == 0 ? Color.RED : Color.GREEN;
}
final int n_dec = n - 1;
for (int i = 0; i < n_dec; ++i) {
final int u = sc.nextInt() - 1;
final int v = sc.nextInt() - 1;
if (u == v) {
continue;
}
edgeMap.get(u).add(v);
edgeMap.get(v).add(u);
}
sc.close();
final Tree[] nodes = new Tree[n];
dfs(x, c, edgeMap, nodes, -1, 0, 0);
return nodes[0];
}
public static void dfs(final int[] x, final Color[] c, final HashMap<Integer, Set<Integer>> edgeMap, final Tree[] tree, final int lastNode, final int currentNode, final int depth) {
final Set<Integer> children = edgeMap.get(currentNode);
if (children.size() <= 1) {
final TreeLeaf leaf = new TreeLeaf(x[currentNode], c[currentNode], depth);
tree[currentNode] = leaf;
} else {
final TreeNode node = new TreeNode(x[currentNode], c[currentNode], depth);
tree[currentNode] = node;
final Iterator<Integer> i = children.iterator();
while (i.hasNext()) {
final int nextNode = i.next();
if (nextNode == lastNode) {
continue;
}
dfs(x, c, edgeMap, tree, currentNode, nextNode, depth + 1);
node.addChild(tree[nextNode]);
}
}
}
public static void main(String[] args) throws FileNotFoundException {
Tree root = solve();
SumInLeavesVisitor vis1 = new SumInLeavesVisitor();
ProductOfRedNodesVisitor vis2 = new ProductOfRedNodesVisitor();
FancyVisitor vis3 = new FancyVisitor();
root.accept(vis1);
root.accept(vis2);
root.accept(vis3);
int res1 = vis1.getResult();
int res2 = vis2.getResult();
int res3 = vis3.getResult();
System.out.println(res1);
System.out.println(res2);
System.out.println(res3);
}
}