题目描述
一棵有 n 个结点，根结点为 1 的二叉树，每条边通过两个顶点x[i],y[i]来描述，每个点的权值通过d[i]来描述。求从根结点到叶子结点路径上所有结点权值乘积对1e9+7取模后最大的路径的值。
思路点拨
从根开始遍历，统计每个到根节点取模后的答案，取最大即可。
考点分析
本题考查的是树的遍历，相信大家都会判断是否是叶节点，不过这里有个坑点就是取的是取模后的最大值，在取模时，由于有负数，需要(a * b % mod + mod) % mod。
参考程序
http://www.jiuzhang.com/solution/maximum-product-path/
/**
* 本参考程序来自九章算法，由 @华助教 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/
public class Solution {
/**
* @param x: The end points of edges set
* @param y: The end points of edges set
* @param d: The weight of points set
* @return: Return the maximum product
*/
long ans;
long mod = 1000000007;
public void dfs(int x, int f, List<List<Integer>>g, long mul,int[] d) {
int isLeaf = 1;
long now = (mul * d[x - 1] % mod + mod) % mod;
for(int i = 0; i < g.get(x).size(); i++) {
int v = g.get(x).get(i);
if(v == f) {
continue;
}
isLeaf = 0;
dfs(v, x, g, now, d);
}
if(isLeaf == 1) {
ans = Math.max(ans, now);
}
}
public int getProduct(int[] x, int[] y, int[] d) {
// Write your code here
int n = d.length;
List<List<Integer>>g = new ArrayList<List<Integer>>();
for(int i = 0; i <= x.length + 1; i++) {
g.add(new ArrayList<Integer>());
}
for(int i = 0; i < x.length; i++) {
g.get(x[i]).add(y[i]);
g.get(y[i]).add(x[i]);
}
ans = -1000000009;
dfs(1, 0, g, 1, d);
return (int)ans;
}
}
