Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3731 Accepted Submission(s): 1886
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 999999999;
struct Node {
int v;
int c;
Node(){}
Node(int V, int C) {
v = V;
c = C;
}
};
int n;
std::vector<Node > v[10010];
int Fmax[10010];//first maxn
int Smax[10010];//second maxn
int visf[10010];//标记最大距离来自的电脑标号
int viss[10010];//标记次大距离来自的电脑标号
void init(int n) {
for (int i=0; i<=n; i++) {
v[i].clear();
}
for (int i=0; i<=n; i++) {
Fmax[i] = Smax[i] = -INF;
}
}
void dfs0(int t, int fa) {
Fmax[t] = 0;
Smax[t] = 0;
for (int i=0; i<v[t].size(); i++) {
Node& kid = v[t][i];
if (kid.v == fa) continue;//cout << t << " " << kid.v <<endl;
dfs0(kid.v, t);
if (Fmax[t] < Fmax[kid.v] + kid.c) {
Smax[t] = Fmax[t];
Fmax[t] = Fmax[kid.v] + kid.c;
viss[t] = visf[t];
visf[t] = kid.v;
}
else if (Smax[t] < Fmax[kid.v] + kid.c) {
Smax[t] = Fmax[kid.v] + kid.c;
viss[t] = kid.v;
}
}
}
void dfs1(int t, int fa, int l) {
if (t != 1) {
if (visf[fa] == t) {
if (Fmax[t] < Smax[fa] + l) {
Smax[t] = Fmax[t];
viss[t] = visf[t];
Fmax[t] = Smax[fa] + l;
visf[t] = fa;
}
else if (Smax[t] < Smax[fa] + l) {
Smax[t] = Smax[fa] + l;
viss[t] = fa;
}
}
else {
if (Fmax[t] < Fmax[fa] + l) {
Smax[t] = Fmax[t];
viss[t] = visf[t];
Fmax[t] = Fmax[fa] + l;
visf[t] = fa;
}
else if (Smax[t] < Fmax[fa] + l) {
Smax[t] = Fmax[fa] + l;
viss[t] = fa;
}
}
}
for (int i=0; i<v[t].size(); i++) {
if (v[t][i].v == fa) continue;
dfs1(v[t][i].v, t, v[t][i].c);
}
}
int main () {
while (cin >> n) {
init(n );
int a, b;
for (int i=2; i<=n; i++) {
cin >> a >> b;
v[i].push_back(Node(a,b));
v[a].push_back(Node(i,b));
}
dfs0(1, -1);
dfs1(1, -1, 0);
for (int i=1; i<=n; i++) {
cout << Fmax[i] <<endl;
}
}
return 0;
}原文:http://blog.csdn.net/xuelanghu407/article/details/43937251