题目大意:
给你N台电脑,这个电脑是树形的,要求求出每台电脑距离他最远的距离是多少?
输入数据:
给你一个N, 这个代表有N台电脑。
接下来 N-1 行,每行两个数字 a, b
第一行代表 第2台电脑和第 a 台电脑直接相连的距离是b.
.......
第n-1行,代表第n台电脑和第an台电脑直接相连,的距离是bn
========================================================================
题目分析:
我们需要做两次DFS, 第一DFS找出每个节点下面子节点的第一大长度和第二大的长度。
第二次DFS,需要比较每个节点的最大长度是由上面的节点过来的,还是和下面节点相连起来长度最大。
==============================================================================
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> #include<queue> #include<vector> #include<map> using namespace std; typedef long long LL; const int INF = 1e9+7; const int maxn = 10010; const int MOD = 1e9+7; struct Node { int e; LL w; Node(int e=0,LL w=0): e(e), w(w) {} }; struct node { int index;/// LL num;/// node(int index = 0,LL num = 0): index(index), num(num){} }One[maxn], Tow[maxn]; LL dp[maxn]; vector<vector<Node> >G; void GetMax(node& A,node& B,node C) { if(A.num < C.num) B = A, A = C; else if(B.num < C.num) B = C; } void DFS(int root) { int len = G[root].size(); for(int i=0; i<len; i++) { int v = G[root][i].e; LL w = G[root][i].w; DFS(v); GetMax(One[root], Tow[root], node(v,One[v].num+w) ); } } void TreeDp(int root,LL W) { dp[root] = W; int flag = 0; if(dp[root] > One[root].num) flag = 1; else dp[root] = One[root].num; int len = G[root].size(); for(int i=0; i<len; i++) { int e = G[root][i].e; LL w = G[root][i].w; if(flag == 1) TreeDp(e, dp[root]+w); else { if(One[root].index == e) TreeDp(e, max(Tow[root].num, W)+w); else TreeDp(e, dp[root] + w); } } } int main() { int n; while( scanf("%d", &n) != EOF) { G.clear(); G.resize(n+5); memset(dp, 0, sizeof(dp)); memset(One, 0, sizeof(One)); memset(Tow, 0, sizeof(Tow)); for(int i=2; i<=n; i++) { int e, w; scanf("%d %d", &e, &w); G[e].push_back(Node(i,w)); } DFS(1); TreeDp(1, 0); for(int i=1; i<=n; i++) printf("%I64d ", dp[i]); } return 0; } /* 4 1 1 2 1 3 1 */