题意描述

[NOI2003]逃学的小孩

找到一颗树上的三个点 \((a,b,c)\)，使得 \(dis(a,b)+dis(a,c)\) 最大，且 \(dis(b,c)>dis(a,c)\)。

算法分析

首先你要看出这是一颗树，因为可以保证，任两个居住点间有且仅有一条通路。

然后学过树的直径的同学都知道一个定理：

树上距离一点最远的点一定是树的直径的两端点之一，次远的点就是另一个端点

所以先两边 DFS 找到树的直径，然后枚举每一个端点求最大值即可。

代码实现

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#define N 200010
using namespace std;

int n,m,head[N],cnt=0,st,ed;
long long dis[N],dis1[N],dis2[N];
struct Edge{
	int nxt,to,val;
}edge[N<<1];

int read(){
	int x=0,f=1;char c=getchar();
	while(c<‘0‘ || c>‘9‘) f=(c==‘-‘)?-1:1,c=getchar();
	while(c>=‘0‘ && c<=‘9‘) x=x*10+c-48,c=getchar();
	return x*f;
}

void add(int u,int v,int w){
	edge[++cnt].nxt=head[u];
	edge[cnt].to=v;
	edge[cnt].val=w;
	head[u]=cnt;
	return;
}

void dfs1(int u,int fa){
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to,w=edge[i].val;
		if(v==fa) continue;
		dis[v]=dis[u]+w;
		if(dis[v]>dis[st]) st=v;
		dfs1(v,u);
	}
	return;
}

void dfs2(int u,int fa){
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to,w=edge[i].val;
		if(v==fa) continue;
		dis1[v]=dis1[u]+w;
		if(dis1[v]>dis1[ed]) ed=v;
		dfs2(v,u);
	}
	return;
}

void dfs3(int u,int fa){
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to,w=edge[i].val;
		if(v==fa) continue;
		dis2[v]=dis2[u]+w;
		dfs3(v,u);
	}
	return;
}

int main(){
	n=read(),m=read();
	int u,v,w;
	for(int i=1;i<=m;i++){
		u=read(),v=read(),w=read();
		add(u,v,w),add(v,u,w);
	}
	dfs1(1,0);
	dfs2(st,0);
	dfs3(ed,0);
	long long ans=dis1[ed],jl=0;
	for(int i=1;i<=n;i++)
		jl=max(jl,min(dis1[i],dis2[i]));
	printf("%lld\n",ans+jl);
	return 0;
}

完结撒花

[NOI2003]逃学的小孩

原文：https://www.cnblogs.com/lpf-666/p/12735068.html