[提交记录]

C++14 O2 TLE, C++ 20 O2 AC

(https://www.luogu.com.cn/record/161435659)

// Problem: P4149 [IOI2011] Race
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4149
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// Author: Li_Feiy
#include<bits/stdc++.h>
#define arrout(a,n) rep(i,1,n)std::cout<<a[i]<<" "
#define arrin(a,n) rep(i,1,n)a[i]=read()
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dep(i,x,n) for(int i=x;i>=n;i--)
#define erg(i,x) for(int i=head[x];i;i=e[i].nex)
#define dbg(x) std::cout<<#x<<":"<<x<<" "
#define mem(a,x) memset(a,x,sizeof a)
#define all(x) x.begin(),x.end()
#define arrall(a,n) a+1,a+1+n
#define PII std::pair<int,int>
#define m_p std::make_pair
#define u_b upper_bound
#define l_b lower_bound
#define p_b push_back
#define CD const double
#define CI const int
#define int long long
#define il inline
#define ss second
#define ff first
#define itn int
int read() {
    char ch=getchar();
    int r=0,w=1;
    while(ch<'0'||ch>'9') w=ch=='-'?-1:w,ch=getchar();
    while(ch>='0'&&ch<='9') r=r*10+ch-'0',ch=getchar();
    return r*w;
}
CI N=2e5+5,INF=1e8+5;
int n,k,rt,tot,sum,ans=INF,max[N],vis[N],dis[N],dist[N],size[N],head[N];
std::queue<int> t;
std::unordered_map<int,int> cnt,cntt;
struct edge {
	int to,nex,data;
}e[N<<1];
void add(int x,int y,int z) {
	e[++tot].to=y;
	e[tot].data=z;
	e[tot].nex=head[x];
	head[x]=tot;
}
void update_size(int x,int fa) {
	size[x]=1;
	max[x]=0;
	erg(i,x) {
		int y=e[i].to;
		if(y==fa||vis[y]) continue;
		update_size(y,x);
		size[x]+=size[y];
		max[x]=std::max(max[x],size[y]);
	}
	max[x]=std::max(max[x],sum-size[x]);
	if(max[x]<max[rt]) rt=x;
}
void update_dist(int x,int fa,int deep) {
	dis[++dis[0]]=dist[x];
	if(cnt[dist[x]]) {
		cnt[dist[x]]=std::min(cnt[dist[x]],deep);
	} else {
		cnt[dist[x]]=deep;
	}
	erg(i,x) {
		int y=e[i].to,z=e[i].data;
		if(y==fa||vis[y]) continue;
		dist[y]=dist[x]+z;
		update_dist(y,x,deep+1);
	}
}
void dfs(int x,int fa) {
	t.push(0);
	vis[x]=1;
	erg(i,x) {
		int y=e[i].to,z=e[i].data;
		if(y==fa||vis[y]) continue;
		dist[y]=z;
		update_dist(y,x,1);
		rep(i,1,dis[0]) {
			if((k>dis[i]&&cntt[k-dis[i]])||k==dis[i]) {
				// dbg(dis[i]),dbg(cnt[dis[i]]),dbg(cntt[k-dis[i]]),puts("");
				ans=std::min(ans,cnt[dis[i]]+cntt[k-dis[i]]);
			}
		}
		rep(i,1,dis[0]) {
			if(cntt[dis[i]]) {
				cntt[dis[i]]=std::min(cntt[dis[i]],cnt[dis[i]]);
			} else {
				cntt[dis[i]]=cnt[dis[i]];
			}
			t.push(dis[i]);
			cnt[dis[i]]=INF;
		}
		dis[0]=0;
	}
	while(!t.empty()) cntt[t.front()]=0,t.pop();
	erg(i,x) {
		int y=e[i].to;
		if(y==fa||vis[y]) continue;
		sum=size[y];
		rt=0;
		max[rt]=INF;
		update_size(y,x);
		update_size(rt,-1);
		dfs(rt,x);
	}
}
signed main() {
	n=read(),k=read();
	rep(i,1,n-1) {
		int x=read(),y=read(),z=read();
		x++,y++;
		add(x,y,z);
		add(y,x,z);
	}
	sum=n;
	rt=0;
	max[rt]=INF;
	update_size(1,-1);
	update_size(rt,-1);
	dfs(rt,-1);
	// dbg(ans);
	std::cout<<(ans>n?-1:ans);
    return 0;
}