P2491 消防/P1099 树网的核

双倍经验，双倍快乐。

题意

在一个树上选择一段总长度不超过\(s\)的链使所有点到该链距离的最大值最小。

输出这个最小的值。

做法

Define:以下\(s\)指链或链长。

证明一下\(s\)一定处于直径上。假设它不在直径上，一定存在直径的其中一个端点到\(s\)的距离大于现在所处支链的最大距离。所以\(s\)不在直径上一定不优。
于是我们找到直径并记录下直径上的所有点。
然后，我们枚举直径上的每一个长度小于\(s\)的最长区间（最长原因显然，因为长度越短答案肯定不会更优），并计算此时的答案，对于每一个区间的答案取min即可。
考虑计算每个区间的答案。我们把直径拉出来，用两个指针\(l\)和\(r\)从左向右遍历这个直径，\(s\)即为\(l\)到\(r\)。考虑此时这个区间的答案即为\(l\)到\(r\)中每个点\(i\)的子树中最深的点的距离（我们设为\(h_i\)）（注意这里的子树是不包括直径的，即子树中所有的点都属于支链）和\(l\)到直径左端点的距离（设为\(ls\)）和\(r\)到直径右端点的距离（设为\(rt\)）的最大值。原因显然。
那么我们可以预处理出\(h_i\)，并在遍历直径的时候用单调队列维护\(h\)的最大值，然后用这个值与\(ls\)和\(rt\)的最大值更新答案（取最小值）即可。

一些疑问

当存在多条直径时，区间似乎一定包括重心并尽量使重心居中。然而这并没有什么卵用，并且一样可以用上面的方法做，不会造成影响。
\(s\)的左右两端一定在端点上。既是，\(s\)是可以为一个点的。

具体实现和代码

求直径时两次DFS即可。然后发现记录的d数组刚好可以用来当做前缀和（只是使代码略显凌乱罢了）
单调队列似乎要特殊记录一下链首的位置而不能用head代替，否则无法记录区间长（或者只是我没有想到更好的处理方法）
求深度DFS或BFS.
时间复杂度O(n).

（学会了一个新单词diameter，意思是直径，重音在|a|上）

#include<iostream>

#include<cstdio>

#include<cctype>

#include<algorithm>

#include<cstring>

using namespace std;

inline int read(){

	int x=0,w=0;char c=getchar();

	while(!isdigit(c))w|=c=='-',c=getchar();

	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();

	return w?-x:x;

}

namespace star

{

	const int maxn=3e5+10;

	int n,l;

	int ecnt,head[maxn],nxt[maxn<<1],to[maxn<<1],dis[maxn<<1];

	inline void addedge(int a,int b,int c){

		to[++ecnt]=b,nxt[ecnt]=head[a],head[a]=ecnt;dis[ecnt]=c;

		to[++ecnt]=a,nxt[ecnt]=head[b],head[b]=ecnt;dis[ecnt]=c;

	}

	int d[maxn],mx,fa[maxn],diam[maxn],tot,sum;

	void dfs1(int x,int f,int &dia){

		fa[x]=f;

		if(mx<d[x])

			mx=d[x],dia=x;

		for(int i=head[x];i;i=nxt[i]){

			int u=to[i];

			if(u==f)continue;

			d[u]=d[x]+dis[i];

			dfs1(u,x,dia);

		}

	}

	inline void diameter(){

		int dia,dia2;

		dfs1(1,0,dia);

		mx=0;d[dia]=0;

		dfs1(dia,0,dia2);

		while(dia2!=dia){

			diam[++tot]=dia2;

			dia2=fa[dia2];

		}

		diam[++tot]=dia;

	}

	int h[maxn],dep[maxn],q[maxn],ans=0x3f3f3f3f;

	void dfs2(int x,int f){

		for(int i=head[x];i;i=nxt[i]){

			int u=to[i];

			if(u==f)continue;

			dfs2(u,x);

			dep[x]=max(dep[x],dep[u]+dis[i]);

		}

	}

	inline void solve(){

		for(int i=2;i<tot;i++){

			int x=diam[i];

			h[i]=0;dep[x]=0;

			for(int j=head[x];j;j=nxt[j]){

				int u=to[j];

				if(u==diam[i-1] or u==diam[i+1])continue;

				dfs2(u,x);

				h[i]=max(h[i],dep[u]+dis[j]);

			}

		}

		int s=1,t=0,ls=0,rt=mx,from=1;

		for(int i=1;i<=tot;i++){

			while(s<=t and d[diam[from]]-d[diam[i]]>l)from++,s+=(from>q[s]),ls=(mx-d[diam[from]]);

			while(s<=t and h[i]>h[q[t]])t--;

			q[++t]=i;rt=d[diam[i]];

			ans=min(ans,max(h[q[s]],max(ls,rt)));

		}

		printf("%d",ans);

	}

	inline void work(){

		n=read(),l=read();

		for(int a,b,c,i=1;i<n;i++)a=read(),b=read(),c=read(),addedge(a,b,c);

		diameter();

		solve();

	}

}

signed main(){

	star::work();

	return 0;

}

巴特西

P2491 消防/P1099 树网的核

P2491 消防/P1099 树网的核

题意

做法

一些疑问

具体实现和代码

最新文章

热门文章