招商银行信用卡中心第二题
第二题没有写完，自测没问题，从每个孩子节点自底向上遍历到根节点为止，一路权值累加，若权值比当前节点的结果大就更新结果。感觉不需要递归和dp，不知道这样思路是不是对的，可以和大家探讨一下：
import java.util.Scanner;
public class Main {
public static class TNode{
int parent;
int weight;
int res;
public TNode(int parent, int weight) {
this.parent = parent;
this.weight = weight;
this.res = 0;
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
TNode[] tree = new TNode[n+1];
for (int i=1; i<n; i++){
int parent = in.nextInt();
int son = in.nextInt();
int weight = in.nextInt();
tree[son] = new TNode(parent, weight);
}
tree[1] = new TNode(-1, 0);
for (int i=tree.length-1; i>=1; i--){
int value = 0;
int j = i;
while (j != -1){
tree[j].res = Math.max(value,tree[j].res);
value += tree[j].weight;
j = tree[j].parent;
}
}
for (int i=1; i<tree.length; i++){
if (i != 1){
System.out.printf(" ");
}
System.out.printf(String.valueOf(tree[i].res));
}
System.out.printf("\n");
}
}
} 
投递腾讯等公司8个岗位 >