2000元阿里云代金券免费领取，2核4G云服务器仅664元/3年，新老用户都有优惠，立即抢购>>>
阿里云采购季（云主机223元/3年）活动入口：请点击进入>>>，
阿里云学生服务器（9.5元/月）购买入口：请点击进入>>>，
描述
有一棵n个节点的树，节点编号是0至n?1，其中0号节点是根节点，i号节点的父亲节点是father[i]。现在要对树浇水，把水撒到根节点上，水会顺着每一条边流下去，从i号节点的父亲流到i号节点需要time[i]的时间，请问需要多久水才能流到所有节点上。
- 2≤n≤105
- 0≤father[i]<n,father[0]=?1
- 1≤times[i]≤1000,time[0]=?1
在线评测地址：领扣题库官网
样例1
输入:
[-1,0,0]
[-1,3,5]
输出:
5
解释:
这棵树如下所示：
0
3/\5
1 2
从0到1需要花费3个单位时间，从0到2需要花费5个单位时间，因此花费5个单位时间可以让水流到所有节点上。解题思路
从根节点向下 bfs，每次记录时间即可。
public class Solution {
/**
* @param father: the father of every node
* @param time: the time from father[i] to node i
* @return: time to flower tree
*/
public int timeToFlowerTree(int[] father, int[] time) {
// write your code here
int n = father.length;
//ArrayList G[] = new ArrayList[n];
ArrayList<ArrayList<Integer>> G= new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < n; i++){
G.add(new ArrayList<Integer>());
}
for (int i = 1; i < n; i++){
G.get(father[i]).add(i);
}
int maxx = 0;
Queue<Integer> eqnode = new LinkedList<Integer>();
Queue<Integer> eqtime = new LinkedList<Integer>();
eqnode.offer(0);
eqtime.offer(0);
while (!eqnode.isEmpty()){
int curnode = eqnode.poll();
int curtime = eqtime.poll();
maxx = Math.max(maxx, curtime);
for (int v: G.get(curnode)){
eqnode.offer(v);
eqtime.offer(curtime + time[v]);
}
}
return maxx;
}
}更多题解参考：九章官网solution
