【悬关】淀粉质 90pts WA 求助
查看原帖
【悬关】淀粉质 90pts WA 求助
743811
Shakespeare07楼主2023/8/31 15:33
#include<bits/stdc++.h>
using namespace std;
#define int long long

int read(){
	int s=0,w=1; char c=getchar();
	while(!isdigit(c)){ if(c=='-') w=-1; c=getchar();}
	while(isdigit(c)){ s=(s<<3)+(s<<1)+(c^48); c=getchar();}
	return s*w;
}
void chkmax(int &x,int y){
	if(y>x) x=y;
}
void chkmin(int &x,int y){
	if(y<x) x=y;
}

const int N=4e5+5;
const int inf=0x3f3f3f3f3f3f3f3f;

int n,m,vis[N],sizeall;
#define fi first
#define se second
vector<pair<int,int> > g[N];

int sz[N],mx[N],rt;
void getrt(int x,int fa){
	sz[x]=1; mx[x]=0;
	for(auto t:g[x]){
		int y=t.fi;
		if(y==fa || vis[y]) continue;
		getrt(y,x);
		sz[x]+=sz[y];
		chkmax(mx[x],sz[y]);
	}
	chkmax(mx[x],sizeall-mx[x]);
	if(mx[x]<mx[rt]) rt=x;	
}

int dep[N],dist[N];
vector<int> v;
int tong[N*10],bh[N];
void getdis(int x,int fa){
	if(dist[x]>m) return;
	v.push_back(dist[x]);
	bh[v.size()-1]=x;
	for(auto t:g[x]){
		int y=t.fi;
		if(y==fa || vis[y]) continue;
		dep[y]=dep[x]+1;
		dist[y]=dist[x]+t.se;
		getdis(y,x);
	}
}

int ans=inf;
int rub[N],tmp;
void calc(int x){
	tmp=0;
	for(auto t:g[x]){
		int y=t.fi;
		if(vis[y]) continue;
		
		v.clear();
		dep[y]=1;
		dist[y]=t.se;
		getdis(y,x);
		
		for(int i=0;i<(int)v.size();++i){
			int kk=v[i];
			if(m-kk>=0) chkmin(ans,tong[m-kk]+dep[bh[i]]);
		}
		for(int i=0;i<(int)v.size();++i){
			int kk=v[i];
			chkmin(tong[kk],dep[bh[i]]);
			rub[++tmp]=kk;
		}
	}
	for(int i=1;i<=tmp;++i) tong[rub[i]]=inf;
}

void solve(int x){
	vis[x]=1;
	calc(x);
	for(auto t:g[x]){
		int y=t.fi;
		if(vis[y]) continue;
		mx[rt=0]=n;
		sizeall=sz[y];
		getrt(y,x);
		solve(rt);
	}
}

signed main(){
//	freopen("123.txt","r",stdin);
//	freopen("123.out","w",stdout);
	
	n=read(),m=read();
	for(int i=1;i<n;++i){
		int x=read(),y=read(),z=read();
		++x,++y;
		g[x].push_back(make_pair(y,z));
		g[y].push_back(make_pair(x,z));
	}
	
	memset(tong,0x3f,sizeof tong);
	mx[rt=0]=n;
	sizeall=n;
	getrt(1,0);
	solve(rt);
	
	if(ans<n) cout<<ans<<endl;
	else puts("-1");
	
	return 0;
}
/*
4 3
0 1 1
1 2 2
1 3 4
*/
2023/8/31 15:33
加载中...