树的直径 两次bfs

树的直径

定义 : 树中所有最短路径的最大值即为树的直径

性质 :

性质A: 设任意一点 U U U的最远的节点为 V V V,则 V V V一定是直径某个端点

性质B: 树的所有直径有一个公共交点
(这是某个大佬的博客的截图,太久了不知道原链接在哪里了)

求法 :

  • 两次 b f s bfs bfs (无法求负边权的树直径)
    • 任选一个点 S S S开始bfs到它的最远距离 V V V
    • 再从 V V V开始 b f s bfs bfs到距离 V V V的最远点 U U U
    • U , V U,V U,V就是直径两端点
  • 树型 D P DP DP (不会)

例题:

  • 求树上所有点的最远点hdu2196

模板

  • 两次bfs求树直茎

    struct Node {
    	int v, step;
    } ;
    struct Edge {
    	int to, w;
    } ;
    vector<Edge> G[MAXN];
    int bfs(int S) { //bfs返回距离起点S最远的点
    	queue<Node> q;
    	memset(vis, false, sizeof(vis));
    	q.push({ S, 0 });
    	vis[S] = true;
    	int tstep = 0/*当前最远距离*/, ret = S;
    	while(!q.empty()) {
    		auto no = q.front(); q.pop();
    		int u = no.v;
    		if(no.step > tstep) {
    			tstep = no.step;
    			ret = u;
    		}
    		for(auto ed : G[u]) {
    			int v = ed.to, w = ed.w;
    			if(!vis[v]) 
                  q.push({v, no.step+w}),
              	  vis[v] = true;
    		}
    	}
    	return ret;
    }
    
hdu2196

给定一颗树,打印树上每个点的最远点代码

  • 利用性质 A A A : 先求直径两端点 U , V U,V U,V,
  • U U U点开始 d f s dfs dfs求每个点到 U U U的距离
  • 再从 V V V点开始 d f s dfs dfs更新最大距离

完整代码

#define debug
#ifdef debug
#include <time.h>
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN ((int)1e4+7)
#define ll long long 
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

namespace FastIO {

	char print_f[105];
	void read() { }
	void print() { putchar('\n'); }

	template <typename T, typename... T2>
		inline void read(T &x, T2 &... oth) {
			x = 0;
			char ch = getchar();
			ll f = 1;
			while (!isdigit(ch)) {
				if (ch == '-') f *= -1; 
				ch = getchar();
			}
			while (isdigit(ch)) {
				x = x * 10 + ch - 48;
				ch = getchar();
			}
			x *= f;
			read(oth...);
		}
	template <typename T, typename... T2>
		inline void print(T x, T2... oth) {
			ll p3=-1;
			if(x<0) putchar('-'), x=-x;
			do{
				 print_f[++p3] = x%10 + 48;
			} while(x/=10);
			while(p3>=0) putchar(print_f[p3--]);
			putchar(' ');
			print(oth...);
		}
} // namespace FastIO
using FastIO::print;
using FastIO::read;

int n, m, Q, K, U, V, ans[MAXN];
bool vis[MAXN];

struct Node {
	int v, step;
} ;

struct Edge {
	int to, w;
} ;
vector<Edge> G[MAXN];

void init() {
	for(int i=1; i<=n+1; i++) 
		G[i].clear(), vis[i] = false, ans[i] = 0;
}

int bfs(int S) { //bfs返回距离起点S最远的点
	queue<Node> q;
	memset(vis, false, sizeof(vis));
	q.push({ S, 0 });
	vis[S] = true;
	int tstep = 0/*当前最远距离*/, ret = S;
	while(!q.empty()) {
		auto no = q.front(); q.pop();
		int u = no.v;
		if(no.step > tstep) {
			tstep = no.step;
			ret = u;
		}
		for(auto ed : G[u]) {
			int v = ed.to, w = ed.w;
			if(!vis[v]) q.push({v, no.step+w}), vis[v] = true;
		}
	}
	return ret;
}

void dfs(int u, int fa, int level) {
	ans[u] = max(ans[u], level); //更新u到直径两端的最远距离
	for(auto ed : G[u]) {
		int v = ed.to, w = ed.w;
		if(fa != v) dfs(v, u, level+w);
	}
}

signed main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	while(~scanf("%d ", &n)) {
		init();
		int u, v, w;
		for(int i=2; i<=n; i++) {
			u = i;
			scanf("%d %d ", &v, &w);
			G[u].push_back({v, w}), G[v].push_back({u, w});
		}
#if 0
		for(int i=1; i<=n; i++) {
			printf("%d : ", i);
			for(auto ed : G[i])
				printf("->%d", ed.to);
			printf("\n");
		}
#endif
		u = bfs(v); //两次bfs求出树的直径
		v = bfs(u);
		U = u, V = v; //树的直径分别为
// show(U, V);
		vis[U] = true;
		dfs(U, -1, 0); //从直径两端点分别dfs
		vis[V] = true;
		dfs(V, -1, 0);
		for(int i=1; i<=n; i++)
			printf("%d\n", ans[i]);
	}





#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}


全部评论

相关推荐

鬼迹人途:你去投一投尚游游戏,服务器一面,第一个图算法,做完了给你一个策略题,你给出方案他就提出低概率问题,答不上当场给你挂
点赞 评论 收藏
分享
就前几天旅游的时候,打开抖音就经常刷到这类视频:以前是高学历学生、老师、主持人,现在做着团播、擦边主播的工作,以及那些经过精心包装的“职业转型”故事——从铺天盖地的VLOG到所谓的“04年夜场工作日记”,这些内容在初中升学、高考放榜等关键时间节点持续发酵。可以说非常直接且精准地在潜移默化地影响着心智尚未成熟的青少年,使其对特殊行业逐渐脱敏。那我就想问了:某些传播公司、平台运营者甚至某些夜场的老板,你们究竟在传递怎样的价值观?点开那些视频,评论区里也是呈现明显的两极分化:一种是​​经济下行论​​:“现在就业市场已经艰难到这种程度了吗?”​​一种是事实反驳派​​:这些创作者往往拥有名校背景,从事着...
牛客刘北:被环境教育的,为了能拿到足够的钱养活自己,不甘心也得甘心,现在的短视频传播的思想的确很扭曲,但是很明显,互联网玩上一年你就能全款提A6,但你全心全意不吃不喝工作一年未必能提A6,但是在高考中考出现这个的确很扭曲,在向大家传播“不上学,玩互联网也可以轻松年入百万”,不是人变了,是社会在变
预测一下26届秋招形势
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务