萌新刚学淀粉质,3TLE和2RE求助
查看原帖
萌新刚学淀粉质,3TLE和2RE求助
774854
qzmoot楼主2024/11/5 19:19
#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
using namespace std;
const int N=2e5+5,V=5e7+5,inf=INT_MAX;
int n,m,cut[V];
int siz[N];
bitset<N>vis;
int ans;
int qu[N],size,maxp[N];
int tot,rt,dis[N];
vector<int>q;
vector<pii>e[N],tmp;
inline void find_w(int u,int fa)
{
	siz[u]=1;
	maxp[u]=1;
	for(auto v:e[u])
	{
		if(v.fi==fa || vis[v.fi])
			continue;
		find_w(v.fi,u);
		siz[u]+=siz[v.fi];
		maxp[u]=max(maxp[u],siz[v.fi]);
	}
	maxp[u]=max(maxp[u],tot-siz[u]);
	if(maxp[u]<maxp[rt])
		rt=u;
}
inline void find_d(int u,int fa,int dep)
{
	tmp.pb(mp(dis[u],dep));
	for(auto v:e[u])
	{
		if(v.fi==fa || vis[v.fi])
			continue;
		dis[v.fi]=dis[u]+v.se;
		find_d(v.fi,u,dep+1);
	}
}
inline void calc(int u)
{
	q.clear();
	for(auto v:e[u])
	{
		if(vis[v.fi])
			continue;
		tmp.clear();
		dis[v.fi]=v.se;
		find_d(v.fi,u,1);
		for(auto j:tmp)
			if(m>=j.fi)
				ans=min(ans,cut[m-j.fi]+j.se);
		for(auto j:tmp)
			q.pb(j.fi),cut[j.fi]=min(cut[j.fi],j.se);
	}
	for(auto i:q)
		cut[i]=inf;
}
inline void solve(int u)
{
	vis[u]=1;
	cut[0]=0;
	calc(u);
	for(auto v:e[u])
	{
		if(vis[v.fi])
			continue;
		tot=siz[v.fi];
		maxp[rt=0]=V;
		find_w(v.fi,0);
		solve(rt);
	}
}
template<typename T>
inline void rd(T &x)
{
	x=0;
	char ch=getchar();
	while(ch<'0' || ch>'9')ch=getchar();
	while(ch>='0' && ch<='9')x=x*10+ch-48,ch=getchar();
}
template<typename T,typename ...Args>
inline void rd(T &x,Args &... args)
{
	rd(x),rd(args...);
}
template<typename T>
inline void wr(T x)
{
	if(x<=9)
		putchar(x+48);
	else
		wr(x/10),putchar(x%10+48); 
}
int main()
{
#ifdef ONLINE_JUDGE
#else
	freopen("data.in","r",stdin);
	freopen("ans.out","w",stdout);
#endif
	rd(n,m);
	ans=n+1;
	vis.reset();
	for(int i=1;i<n;i++)
	{
		int u,v,w;
		rd(u,v,w);
		e[u].pb(mp(v,w)),e[v].pb(mp(u,w));
	}
	memset(cut,0x7f,sizeof cut);
	maxp[rt=0]=n;
	tot=n;
	find_w(1,0);
	solve(rt);
	if(ans!=n+1)wr(ans);
	else puts("-1");
	cerr<<(double)clock()/(double)CLOCKS_PER_SEC;
	return 0; 
}
2024/11/5 19:19
加载中...