首页 > 代码库 > SGU 149. Computer Network
SGU 149. Computer Network
时间限制:0.25s
空间限制:4M;
题意:
给出一颗n(n<=10000)个节点的树,和n-1条边的长度。求出这棵树每个节点到最远节点的距离;
Solution:
对于一个节点,我们可以用DFS,在O(n)的时间内求出它的最远节点的距离.
显然对于10000个节点,不可能将每一个节点都这样求.
那么我们来看看,对于一个已经求过的节点我们可以做什么:
假设,有节点k,他有子节点p,两者距离为d
已经求得它的最远节点距离为dis1,
这时对他的子节点p来说,有两种情况:
一种是:p在k的与最远节点的路径上.
这时p的最远距离等于max(dis1-d,p的次远距离+d);
另一种是:p不在k的最远路径上.
此时p的最远距离等于max(dis1+d,p向下的最远距离);
通过上面我们发现,我们需要一个节点的最远距离和次远距离以及p向下的最远距离.
幸运的是这三个量都可以通过一次对根的DFS在O(n)的时间内求出.
最后再从根进行一次DFS遍求出每个节点的最远距离和次远距离就可以求出所有的答案了.
总的时间复杂度O(n),空间复杂度O(n);
code
#include <iostream>#include <cstdio>#include <vector>#include <utility>using namespace std;#define mp make_pair#define fi first#define se second#define sz(x) ((int) (x).size())#define rd(a) scanf("%d",&a)#define rdd(a,b) scanf("%d%d",&a,&b);#define rep(i,a,b) for(int i=(a);i<=(b);i++)#define pb push_backtypedef pair<int, int> ii;typedef vector<ii> vii;const int INF = 11111;vii edge[INF];int dis[INF][2], ans[INF];int n, x, y;int dfs (int x) { dis[x][0] = 0; rep (i, 0, sz(edge[x]) - 1) { ii v = edge[x][i]; int tem = dfs (v.fi)+v.se; rep (i, 0, 1) if (tem > dis[x][i]) swap (tem, dis[x][i]); } return dis[x][0];}void DP (int x) { int tem; ans[x] = dis[x][0]; rep (i, 0, sz (edge[x]) - 1) { ii v = edge[x][i]; if (dis[v.fi][0] + v.se == dis[x][0]) tem = dis[x][1] + v.se; else tem = dis[x][0] + v.se; rep (i, 0, 1) if (tem > dis[v.fi][i]) swap (tem, dis[v.fi][i]); DP (v.fi); }}int main() { rd (n); rep (i, 2, n) { rdd (x, y); edge[x].pb (mp (i, y) ); } dfs (1); DP (1); rep (i, 1, n) printf ("%d\n", ans[i]);}