记录编号	205483	评测结果	AAAAAAAAAA
题目名称	不平凡的引线	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	1.761 s
提交时间	2015-11-05 14:27:42	内存使用	9.98 MiB

#include<cstdio>
#include<deque>
#include<iostream>
using namespace std;
const int SIZEN=100010,INF=0x7fffffff/2;
deque<pair<int,int> > s[SIZEN];
bool H[SIZEN]={0};
int f[SIZEN]={0};
int w[SIZEN]={0};
int tim[SIZEN]={0};
int ans=0;
int N;
void dfs(int x)
{
	tim[x]=INF;
	for(int i=0;i<s[x].size();i++)
	{
		int v=s[x][i].first,p=s[x][i].second;
		if(v==f[x]) continue;
		f[v]=x;w[v]=p;dfs(v);
	}
}
void dfs2(int x)
{
	if(s[x].size()==1) tim[x]=0;
	for(int i=0;i<s[x].size();i++)
	{
		int v=s[x][i].first;
		if(v==f[x]) continue;
		dfs2(v);
		tim[x]=min(tim[x],tim[v]+w[v]);
	}
}
void dfs3(int x)
{
	for(int i=0;i<s[x].size();i++)
	{
		int v=s[x][i].first;
		if(v==f[x]) continue;
		if(tim[v]>tim[x]+w[v]) tim[v]=tim[x]+w[v];
		else if(tim[v]+w[v]>tim[x])
		{
			int t=tim[v],y=tim[x];
			if(t>y) swap(t,y);
			int c=w[v]-(y-t);
			ans=max(ans,2*y+c);
		}
		dfs3(v);
	}
}
int main()
{
	freopen("firelead.in","r",stdin);
	freopen("firelead.out","w",stdout);
	scanf("%d",&N);
	N++;
	int fr,to,lo;
	int root;
	for(int i=1;i<N;i++)
	{
		scanf("%d%d%d",&fr,&to,&lo);
		s[fr].push_back(make_pair(to,lo));
		s[to].push_back(make_pair(fr,lo));
	}
	for(int i=1;i<=N;i++) if(s[i].size()>2) {root=i;break;}
	dfs(root);
	//for(int i=1;i<=N;i++) cout<<f[i]<<" "<<w[i]<<endl;
	dfs2(root);
	//for(int i=1;i<=N;i++) cout<<tim[i]<<endl;
	dfs3(root);
	for(int i=1;i<=N;i++)
	{
		ans=max(ans,2*tim[i]);
	}
	double now=(ans+0.0)/2;
	printf("%.1lf",now);
	return 0;
}