【BZOJ1999】【NOIP2007】树网的核

一开始觉得这是个什么神题

然后搜题解发现写什么Floyd+模拟O(n³)。。好**的方法

不想写。。然后写了个O(n)

可过BZOJ加强的500000数据。。

// <core.cpp> - 03/01/16 20:38:46
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
const int MAXN=500001;
const int INF=1000000000;
vector <pair<int,int> >b[MAXN];
int dis[MAXN],f[MAXN];
bool zj[MAXN];
void dfs(int x){
	for(int i=0;i<b[x].size();i++){
		int next=b[x][i].first;
		if(next==f[x]||zj[next])continue;
		f[next]=x;
		dis[next]=dis[x]+b[x][i].second;
		dfs(next);
	}
}
int main(){
	freopen("core.in","r",stdin);
	freopen("core.out","w",stdout);
	int n=getint(),s=getint();
	for(int i=1;i<=n-1;i++){
		int u=getint(),v=getint(),w=getint();
		b[u].push_back(make_pair(v,w));
		b[v].push_back(make_pair(u,w));
	}
	int l=1,l2=1;
	dis[1]=0;dfs(1);
	for(int i=1;i<=n;i++){f[i]=0;if(dis[i]>dis[l])l=i;}//得到一个端点
	dis[l]=0;dfs(l);
	for(int i=1;i<=n;i++)if(dis[i]>dis[l2])l2=i;//得到第二个端点
	int ans=INF,j=l2;
	for(int i=l2;i;i=f[i]){
		while(f[j]&&dis[i]-dis[f[j]]<=s)j=f[j];
		ans=min(ans,max(dis[j],dis[l2]-dis[i]));//自行脑补
	}
	for(int i=l2;i;i=f[i])zj[i]=1;
	for(int i=l2;i;i=f[i])dis[i]=0,dfs(i);
	for(int i=1;i<=n;i++)ans=max(ans,dis[i]);//自行脑补
	printf("%d",ans);
	return 0;
}

// <core.cpp> - 03/01/16 20:38:46

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=500001;

const int INF=1000000000;

vector <pair<int,int> >b[MAXN];

int dis[MAXN],f[MAXN];

bool zj[MAXN];

void dfs(int x){

for(int i=0;i<b[x].size();i++){

int next=b[x][i].first;

if(next==f[x]||zj[next])continue;

f[next]=x;

dis[next]=dis[x]+b[x][i].second;

dfs(next);

}

int main(){

freopen("core.in","r",stdin);

freopen("core.out","w",stdout);

int n=getint(),s=getint();

for(int i=1;i<=n-1;i++){

int u=getint(),v=getint(),w=getint();

b[u].push_back(make_pair(v,w));

b[v].push_back(make_pair(u,w));

}

int l=1,l2=1;

dis[1]=0;dfs(1);

for(int i=1;i<=n;i++){f[i]=0;if(dis[i]>dis[l])l=i;}//得到一个端点

dis[l]=0;dfs(l);

for(int i=1;i<=n;i++)if(dis[i]>dis[l2])l2=i;//得到第二个端点

int ans=INF,j=l2;

for(int i=l2;i;i=f[i]){

while(f[j]&&dis[i]-dis[f[j]]<=s)j=f[j];

ans=min(ans,max(dis[j],dis[l2]-dis[i]));//自行脑补

}

for(int i=l2;i;i=f[i])zj[i]=1;

for(int i=l2;i;i=f[i])dis[i]=0,dfs(i);

for(int i=1;i<=n;i++)ans=max(ans,dis[i]);//自行脑补

printf("%d",ans);

return 0;

}