题目链接

BZOJ3242

题解

题意很清楚，找一点使得最远点最近

如果是一棵树，就是直径中点

现在套上了一个环，我们把环单独拿出来

先求出环上每个点外向树直径更新答案，并同时求出环上每个点外向的最远距离\(val[i]\)

首先要明白以下事实：

①删掉任意一条边不会使答案更优

②环上存在一条边，使得删掉后答案不变

所以我们要做的就是枚举这条边，然后快速求出断掉后的直径

如何快速求出一棵树的直径？

我们同样在剩余的环上找一个断边，直径只有两种情况：

①在断边的任意一侧

②经过断边

情况①，我们只需令\(g[i]\)表示从断边一端\(x\)到\(i\)所形成的树的直径

则

这个可以用单调队列优化

情况②，令\(f[i]\)表示断边一端\(u\)到\(i\)中\(val[i]\)的最大值

就可以直接求出了

然后问题就解决了

复杂度是\(O(n)\)的

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,int>(a,b)

#define cls(s) memset(s,0,sizeof(s))

#define cp pair<int,int>

#define LL long long int

using namespace std;

const int maxn = 100005,maxm = 100005;

const LL INF = 10000000000000000ll;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

int h[maxn],ne = 1;

struct EDGE{int to,nxt,f; LL w;}ed[maxn << 1];

inline void build(int u,int v,LL w){

	ed[++ne] = (EDGE){v,h[u],1,w}; h[u] = ne;

	ed[++ne] = (EDGE){u,h[v],1,w}; h[v] = ne;

}

int n,c[maxn],ci,incir[maxn],fa[maxn];

LL Lcir,sum[maxn],dep[maxn],Len[maxn],F[maxn];

void dfs(int u){

	Redge(u) if ((to = ed[k].to) != fa[u]){

		if (!dep[to]){

			dep[to] = dep[u] + ed[k].w; fa[to] = u;

			dfs(to);

		}

		else if (dep[to] < dep[u]){

			ed[k].f = ed[k ^ 1].f = 0;

			Lcir = dep[u] - dep[to] + ed[k].w;

			for (int i = u; i != to; i = fa[i]){

				c[++ci] = i;

				sum[ci] = dep[i] - dep[fa[i]];

			}

			c[++ci] = to;

			for (int i = ci; i; i--)

				sum[i] = sum[i - 1];

			for (int i = 1; i <= ci; i++)

				sum[i] += sum[i - 1];

		}

	}

}

LL d[maxn];

int rt;

void DFS(int u,int flag){

	if (d[u] > d[rt]) rt = u;

	Redge(u) if (!incir[to = ed[k].to] && to != fa[u]){

		fa[to] = u; d[to] = d[u] + ed[k].w;

		DFS(to,flag);

		if (flag) F[u] = max(F[u],F[to] + ed[k].w);

	}

}

void dfs1(int u){

	if (d[u] > d[rt]) rt = u;

	Redge(u) if (ed[k].f && (to = ed[k].to) != fa[u]){

		fa[to] = u; d[to] = d[u] + ed[k].w;

		dfs1(to);

	}

}

LL ans,f1[maxn],f2[maxn],g1[maxn],g2[maxn];

LL S[maxn],val[maxn],qv[maxn << 1];

int head,tail;

void work(){

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

		S[i] = sum[i]; val[i] = F[c[i]];

	}

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

		f1[i] = max(f1[i - 1],val[i] + S[i]);

	}

	qv[head = tail = 0] = val[1] - S[1];

	g1[1] = val[1];

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

		g1[i] = max(g1[i - 1],val[i] + S[i] + qv[head]);

		while (head <= tail && val[i] - S[i] >= qv[tail]) tail--;

		qv[++tail] = val[i] - S[i];

	}

	for (int i = ci; i; i--){

		f2[i] = max(f2[i + 1],val[i] + S[ci] - S[i]);

	}

	qv[head = tail = 0] = val[ci] + S[ci];

	g2[ci] = val[ci];

	for (int i =  ci - 1; i; i--){

		g2[i] = max(g2[i + 1],val[i] - S[i] + qv[head]);

		while (head <= tail && val[i] + S[i] >= qv[tail]) tail--;

		qv[++tail] = val[i] + S[i];

	}

	LL ret = INF,len = Lcir - S[ci];

	for (int i = 1; i < ci; i++)

		ret = min(ret,max(f1[i] + f2[i + 1] + len,max(g1[i],g2[i + 1])));

	rt = 1; d[rt] = fa[rt] = 0;

	dfs1(rt);

	d[rt] = 0; fa[rt] = 0;

	dfs1(rt);

	ret = min(ret,d[rt]);

	ans = max(ans,ret);

	//REP(i,ci) printf("%d  f1[] = %lld  f2 = %lld  g1 = %lld  g2 = %lld\n",i,f1[i],f2[i],g1[i],g2[i]);

}

int main(){

	n = read(); int a,b,w;

	REP(i,n) a = read(),b = read(),w = read(),build(a,b,w);

	dep[1] = 1; dfs(1);

	REP(i,ci) incir[c[i]] = true;

	REP(i,ci){

		int u = c[i]; incir[u] = false;

		rt = u ; d[u] = fa[u] = 0;

		DFS(u,1);

		d[rt] = 0; fa[rt] = 0;

		DFS(rt,0);

		Len[u] = d[rt];

		ans = max(ans,Len[u]);

		incir[u] = true;

	}

	work();

	printf("%.1lf\n",ans / 2.0);

	return 0;

}