树的直径小记

我们总是在刷那些常考的算法，却忽略一些冷门算法，以至于一涉及这些就不会。
\(~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\)——题记

读本章所需思维：反证法

定义：树上任意两节点之间最长的简单路径即为树的「直径」

显然，一棵树可以有多条「直径」

一些引理（这里只讨论边权没有负的情况）：

·\(1\)，所有「直径」的中点是同一个

证明：考虑经过的不是同一点，那么一条「直径」的一端到该「直径」的中点再到另一个「直径」的中点再到另一个「直径」的一端一定更优，所以矛盾，古该结论成立。

·\(2\)，从任意节点开始 \(dfs\)，到达的最远节点，必然是直径的一端。

证明：考虑反证法，易证

1.1 试一试

观察题目，我们发现：要找长度和不超过 \(s\) 的路径，所以我们无法树形 \(DP\)（或者说很难）。

那竟然无法从条件入手，那就从目的入手：要求其他所有城市到这条路径的距离的最大值最小，所以我们要找这条路径的性质。

我们发现，这条路径必然包含一些点，因为到这些点最远的点就是树的「直径」的一端，所以我们找的点一定要尽可能接近树的「直径」的两端，所以可以得知这条路被树的「直径」包含。

因为「直径」有多条，考虑找任意一条即可，证明仔细思考即可，很难写

至于找路径可以用单调栈实现

上代码：

#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
const int N=3e5+50;
int n,s,ans=1e9;

int h[N],e[N*2],w[N*2],ne[N*2],idx;
void add(int a,int b,int c)
{
	e[idx]=b;
	w[idx]=c;
	ne[idx]=h[a];
	h[a]=idx++;
}

int dis[N],pre[N],xl[N];
void dfs(int wz,int last,int cd,bool flag)
{
	if(flag) pre[wz]=last,xl[wz]=cd;
	dis[wz]=dis[last]+cd;
	for(int i=h[wz];i!=-1;i=ne[i])
		if(e[i]!=last) dfs(e[i],wz,w[i],flag);
}
int st,en;
void Get_road()
{
	dfs(1,0,0,0);
	for(int i=1,maxdis=0;i<=n;i++)
		if(dis[i]>maxdis) maxdis=dis[i],st=i;
	dfs(st,0,0,1);
	for(int i=1,maxdis=0;i<=n;i++)
		if(dis[i]>maxdis) maxdis=dis[i],en=i;
}

int dis1[N];
void bfs()
{
	memset(dis,0x3f,sizeof dis);
	queue<int> q,from;
	for(int i=en;i!=0;i=pre[i])
		q.push(i),from.push(i),dis[i]=0;
	while(!q.empty())
	{
		int wz=q.front(),fr=from.front();
		q.pop(),from.pop();
		for(int i=h[wz];i!=-1;i=ne[i])
			if(dis[e[i]]==dis[0])
			{
				dis[e[i]]=dis[wz]+w[i];
				dis1[fr]=max(dis1[fr],dis[e[i]]);
				q.push(e[i]);
				from.push(fr);
			}
	}
}

PII que[N];
int sum[N],ks=1,js;
void solve()
{
	for(int i=en;i!=st;i=pre[i])//
		sum[pre[i]]=sum[i]+xl[i];
	for(int l=en,r=en;r!=st&&l!=0;l=pre[l])
	{
		int last=r;
		while(sum[r]-sum[l]<=s&&r!=0)
		{
			last=r,r=pre[r];
			if(r!=0&&sum[r]-sum[l]<=s)
			{
				while(js>=ks&&dis1[r]>=que[js].first) js--;
				que[++js]={dis1[r],r};
			}
		}
		if(r==0||sum[r]-sum[l]>s) r=last;
		int now=max(sum[l],sum[st]-sum[r]);
		now=max(now,que[ks].first);
		ans=min(now,ans);
		if(que[ks].second==l) ks++;
	}
}

int main()
{
	memset(h,-1,sizeof h);
	scanf("%d %d",&n,&s);
	int u,v,w;
	for(int i=1;i<n;i++)
	{
		scanf("%d %d %d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	Get_road();
	bfs();
	solve();
	printf("%d\n",ans);
	return 0;
}

没有一个算法值得轻视，也没有一个算法简单
\(~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\)——后记