淀粉质95pts求条玄关
查看原帖
淀粉质95pts求条玄关
722094
Little_Cancel_Sunny楼主2024/10/5 21:21
#include<bits/stdc++.h>
using namespace std;

const int N=1e7+15;

int h[N],ne[N],to[N],weight[N],idx=0;
int root;
int siz[N],maxw[N];
bool vis[N];
int tot;
int point[N],tree[N];
long long dis[N];
int length[N];
int ans=1e9;
int n,k;

bool cmp(int x,int y)
{
	return dis[x]<dis[y];
}

void add(int u,int v,int w)
{
	ne[++idx]=h[u];
	h[u]=idx;
	to[idx]=v;
	weight[idx]=w;
}

void get_root(int u,int fa,int sizz)
{
	maxw[u]=0;
	siz[u]=1;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int v=to[i];
		if(v==fa||vis[v])
		{
			continue;
		}
		get_root(v,u,sizz);
		siz[u]+=siz[v];
		maxw[u]=max(maxw[u],siz[v]);
	}
	maxw[u]=max(maxw[u],sizz-siz[u]);
	if(!root||maxw[u]<=sizz/2)
	{
		root=u;
	}
}

void get_dis(int u,int fa,int w,int t,int len)
{
	length[u]=len;
	point[++tot]=u;
	tree[u]=t;
	dis[u]=w;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int v=to[i];
		if(v==fa||vis[v])
		{
			continue;
		}
		get_dis(v,u,w+weight[i],t,len+1);
		
	}
}

void get_ans(int u)
{
	tot=0;
	tree[u]=u;
	point[++tot]=u;
	dis[u]=0;
	length[u]=0;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int v=to[i],w=weight[i];
		if(vis[v])
		{
			continue;
		}
		get_dis(v,u,w,v,1);
	}
	sort(point+1,point+tot+1,cmp);
	//sort(length+1,length+tot+1,cmp);
//	cout<<u<<endl;
//	for(int i=1;i<=tot;i++)
//	{
//		cout<<i<<" "<<point[i]<<" "<<length[i]<<" "<<dis[i]<<" "<<tree[point[i]]<<endl;	
//	} 
//	cout<<endl;
	int l=1,r=tot;
	while(l<r)
	{
		//cout<<l<<" "<<r<<endl;
		if(dis[point[l]]+dis[point[r]]<k)
		{
			l++;
		}
		else
		{
			if(dis[point[l]]+dis[point[r]]>k)
			{
				r--;
			}
			else
			{
				if(tree[point[l]]==tree[point[r]])
				{
					if(dis[point[r]]==dis[point[r-1]])
					{
						r--;
					}
					else
					{
						l++;
					}
				}
				else
				{
					//cout<<length[point[l]]+length[point[r]]<<endl;
					
					ans=min(length[point[l]]+length[point[r]],ans);
					if(dis[point[r]]==dis[point[r-1]])
					{
						r--;
					}
					else
					{
						l++;
					}
					//break; 
				}
			}
		}
	}
}

void solve(int u)
{
	vis[u]=true;
	get_ans(u);
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int v=to[i];
		if(vis[v])
		{
			continue;
		}
		root=0;
		get_root(v,u,siz[v]);
		solve(root);
	}
}

int main()
{
	cin.tie(0); 
	cout.tie(0); 
	ios::sync_with_stdio(false);
	memset(h,-1,sizeof h);
	memset(vis,false,sizeof vis);
	cin>>n>>k;
	for(int i=1;i<n;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		u+=1;
		v+=1;
		add(u,v,w);
		add(v,u,w);
	}
	get_root(1,0,n);
	solve(root);
	if(ans==1e9)
	{
		ans=-1;
	}
	cout<<ans<<endl;
	return 0;
}
2024/10/5 21:21
加载中...