P1099 [NOIP2007 提高组] 树网的核

题面

设 \(T=(V,E,W)\) 是一个无圈且连通的无向图（也称为无根树），每条边都有正整数的权，我们称 \(T\) 为树网（treenetwork），其中 \(V\)，\(E\) 分别表示结点与边的集合，\(W\) 表示各边长度的集合，并设 \(T\) 有 \(n\) 个结点。

路径：树网中任何两结点 \(a\)，\(b\) 都存在唯一的一条简单路径，用 \(d(a, b)\) 表示以 \(a, b\) 为端点的路径的长度，它是该路径上各边长度之和。我们称
\(d(a, b)\) 为 \(a, b\) 两结点间的距离。

\(D(v, P)=\min\{d(v, u)\}\), \(u\) 为路径 \(P\) 上的结点。

树网的直径：树网中最长的路径成为树网的直径。对于给定的树网 \(T\)，直径不一定是唯一的，但可以证明：各直径的中点（不一定恰好是某个结点，可能在某条边的内部）是唯一的，我们称该点为树网的中心。

偏心距 \(\mathrm{ECC}(F)\)：树网 \(T\) 中距路径 \(F\) 最远的结点到路径 \(F\) 的距离，即

\(\mathrm{ECC}(F)=\max\{D(v, F),v \in V\}\)

任务：对于给定的树网 \(T=(V, E, W)\) 和非负整数 \(s\)，求一个路径 \(F\)，他是某直径上的一段路径（该路径两端均为树网中的结点），其长度不超过 \(s\)（可以等于 \(s\)），使偏心距 \(\mathrm{ECC}(F)\) 最小。我们称这个路径为树网 \(T=(V, E, W)\) 的核（Core）。必要时，\(F\) 可以退化为某个结点。一般来说，在上述定义下，核不一定只有一个，但最小偏心距是唯一的。

下面的图给出了树网的一个实例。图中，\(A-B\) 与 \(A-C\) 是两条直径，长度均为 \(20\)。点 \(W\) 是树网的中心，\(EF\) 边的长度为 \(5\)。如果指定 \(s=11\)，则树网的核为路径DEFG（也可以取为路径DEF），偏心距为 \(8\)。如果指定 \(s=0\)（或 \(s=1\)、\(s=2\)），则树网的核为结点 \(F\)，偏心距为 \(12\)。

求指定意义下的最小偏心距。

【数据范围】

• 对于 \(40\%\) 的数据，保证 \(n \le 15\)。
• 对于 \(70\%\) 的数据，保证 \(n \le 80\)。
• 对于 \(100\%\) 的数据，保证 \(n \le 300\)，\(0\le s\le10^3\)，\(1 \leq u, v \leq n\)，\(1 \leq w \leq 10^3\)。

简化题意

给定一棵带边权无根树，在其直径上求出一段长度不超过 \(s\) 的路径 \(F\)，使得离路径距离最远的点到路径的距离最短。

鸣谢 题解 P1099 【树网的核】

思路

首先求出树的直径。可以使用众所周知的两遍DFS大法。

先选择任意一个顶点为源点，然后DFS求出最远的点 \(k\)，然后再进行一遍这个操作。得到的就是直径的两个端点。

然后用单调队列的思想，再尺取求答案的最小值。

把直径标记出来，重新计算贡献（偏心距），然后统计答案。

代码

#include 
using namespace std;

int n,m,k,ans=INT_MAX;
int dis[500005],fa[500005],head[500005];
bool flags[500005];

struct edge{
	int next,to,weight;
} e[500005*2];
int ec;

void add(int u,int v,int w){
	e[++ec].to=v;
	e[ec].weight=w;
	e[ec].next=head[u];
	head[u]=ec;
}

void dfs(int father,int x){
	fa[x]=father;
	if(dis[x]>dis[k]){
		k=x;
	}
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].to;
		if(y==father||flags[y]){
			continue;
		}
		dis[y]=dis[x]+e[i].weight;
		dfs(x,y);
	}
}

int main(){
	cin>>n>>m;
	for(int i=1,x,y,z;i>x>>y>>z;
		add(x,y,z);
		add(y,x,z);
	}
	dis[1]=1;
	dfs(0,1);
	dis[k]=0;
	dfs(0,k);
	int top=k;
	for(int i=top,j=top,l=1,r=0;i;i=fa[i]){
		while(dis[j]-dis[i]>m){
			j=fa[j];
		}
        int x=max(dis[top]-dis[j],dis[i]);
        ans=min(ans,x);
	}
	for(int i=top;i;i=fa[i]){
		flags[i]=true;
	}
	for(int i=top;i;i=fa[i]){
		k=i;
		dis[k]=0;
		dfs(fa[i],i);
	}
	for(int i=1;i<=n;i++){
		ans=max(ans,dis[i]);
	}
	cout<