// max weighted path in a tree // #include #include #include #include using namespace std; struct Tnode { int parent; // = -1 if root int weight; // weight of edge to parent vector children; int maxp_endpoint; // max sum starting at node down tree int maxp_other; // max sum in subtree (may not include this node) }; typedef vector WTree; void compute(WTree &T, int root) { int numchild = T[root].children.size(); if (numchild == 0) // is leaf { T[root].maxp_endpoint = T[root].maxp_other = 0; return; } int bestend1 = 0; // keep track of two best child ending paths int bestend2 = 0; // to possible joining for a bestother int bestother = 0; for (int i=0; i bestend1) { bestend2 = bestend1; bestend1 = b1+w; } else if (b1+w > bestend2) { bestend2 = b1+w; } if (b1 > bestother) { bestother = b1; } int b2 = T[child].maxp_other; if (b2 > bestother) { bestother = b2; } } T[root].maxp_endpoint = bestend1; if (numchild >= 2 && bestend1+bestend2 > bestother) T[root].maxp_other = bestend1+bestend2; else T[root].maxp_other = bestother; } int main(int argc, char* argv[]) { int n; // number of nodes int p, w; // parent and weight while (true) { cin >> n; if (n==0) break; WTree T(n); T[0].parent=-1; T[0].weight=0; int i; for (i=1; i> p >> w; assert(p>=0 && p= -1000); T[i].parent = p; T[i].weight = w; T[p].children.push_back(i); } compute(T,0); // for (i=0; i