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_back

typedef 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]);
}

  

              

 

SGU 149. Computer Network,古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。