DSU 萌新 WA*1,TLE* 3 求大佬
查看原帖
DSU 萌新 WA*1,TLE* 3 求大佬
305508
_Galatea_楼主2022/7/23 17:15
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
const int M=2e5+5;
struct edge{
	int t,d;
};
int n,k,sz[M],son[M],S,L[M],R[M],tot,dp[M],dis[M],id[M],ans=2e9;//id:dfs顺序->编号 
vector<edge> g[M];
map<ll,int> mn;                 //路程深度为ll, 树上深度最小为int 
inline void dfs(const int &x,const int &fa,const int &dep,const int &di)
{
	id[tot]=x;L[x]=tot++;dp[x]=dep;dis[x]=di;
	if(x!=0&&g[x].size()==1)
	{
		sz[x]=1;
		R[x]=tot;
		return;
	}
	for(int i=0;i<g[x].size();i++)
	{
		int to=g[x][i].t;
		if(to!=fa){
			dfs(to,x,dep+1,di+g[x][i].d);
			if(sz[x]<sz[to])
			{
				sz[x]=sz[to];
				son[x]=to;
			}
		}
	}
	sz[x]++;
	R[x]=tot;
	return;
}
inline void Add(const int &l,const int &r,const int &f)
{
	int sum=k+2*dis[f];
	for(int i=l;i<r;i++)
	{
		if(S>=0&&L[S]<=i&&i<R[S])
		{
			continue;
		}
		if(mn[dis[id[i]]])mn[dis[id[i]]]=min(dp[id[i]],mn[dis[id[i]]]);
		else{
			mn[dis[id[i]]]=dp[id[i]];
		}
		if(mn[sum-dis[id[i]]]&&mn[dis[id[i]]]){
			ans=min(ans,mn[sum-dis[id[i]]]+mn[dis[id[i]]]-2*dp[f]);
		}
	}
}
inline void Del()
{
	mn.clear();
	return;
}
inline void dsu(const int &x,const int &fa,const bool &op)
{
	for(int i=0;i<g[x].size();i++)
	{
		int to=g[x][i].t;
		if(to!=fa&&to!=son[x]){
			dsu(to,x,0);
		}
	}
	if(son[x]){
		dsu(son[x],x,1);
	}
	S=son[x];
	if(x!=0&&g[x].size()==1)S=-1;
	Add(L[x],R[x],x);
	if(op){
		return;
	}
	else{
		S=-1;
		Del();
		return;
	}
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=0;i<n-1;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		g[u].pb(edge{v,w});
		g[v].pb(edge{u,w});
	}
	dfs(0,0,1,0);
	dsu(0,0,1);
	if(ans!=2e9)printf("%d\n",ans);
	else printf("-1\n");
	return 0;
}
2022/7/23 17:15
加载中...