提交记录

树上启发式合并。不知道为什么答案比正确答案优，求大佬帮忙调一下。

代码如下：

#include <bits/stdc++.h>
#define fin(str) freopen(str,"r",stdin)
#define fout(str) freopen(str,"w",stdout)
#define ll long long
using namespace std;
const int maxn=2e5+5;
const int inf=0x3f3f3f3f;
struct edge{
	int to,w,next;
}e[maxn<<1];
int tot,h[maxn];
inline void addEdge(int x,int y,int z){
	e[++tot]=(edge){y,z,h[x]};
	h[x]=tot;
}
int n,k,ans=inf;
int fa[maxn],dep[maxn],siz[maxn],son[maxn];
ll dis[maxn];
map <ll,int> t;
inline void init(int x,int f,int d){
	siz[x]=1;
	fa[x]=f;
	dep[x]=d;
	int maxx=-1;
	for (int i=h[x];i;i=e[i].next){
		int v=e[i].to;
		if (v==f) continue;
		dis[v]=dis[x]+e[i].w;
		init(v,x,d+1);
		siz[x]+=siz[v];
		if (siz[v]>maxx){
			maxx=siz[v];
			son[x]=v;
		}
	}
}
inline void clear(int x){
	t[dis[x]]=0;
	for (int i=h[x];i;i=e[i].next){
		int v=e[i].to;
		if (v==fa[x]) continue;
		clear(v);
	}
}
inline void add(int x,int rt){
	int org=t[dis[x]];
	if (!org) t[dis[x]]=dep[x];
	else t[dis[x]]=min(org,dep[x]);
	int depth=t[k+dis[rt]*2-dis[x]];
	if (depth) ans=min(ans,dep[x]+depth-dep[rt]*2);
}
inline void update(int x,int rt){
	add(x,rt);
	for (int i=h[x];i;i=e[i].next){
		int v=e[i].to;
		if (v==fa[x]) continue;
		update(v,rt);
	}
}
inline void dfs(int x){
	for (int i=h[x];i;i=e[i].next){
		int v=e[i].to;
		if (v==fa[x] || v==son[x]) continue;
		dfs(v);
		clear(v);
	}
	if (son[x]) dfs(son[x]);
	for (int i=h[x];i;i=e[i].next){
		int v=e[i].to;
		if (v==fa[x] || v==son[x]) continue;
		update(v,x);
	}
	add(x,x);
}
int main(){
	scanf("%d%d",&n,&k);
	for (int i=1,x,y,z;i<n;i++){
		scanf("%d%d%d",&x,&y,&z),x++,y++;
		addEdge(x,y,z);
		addEdge(y,x,z);
	}
	init(1,0,1);
	dfs(1);
	printf("%d\n",(ans==inf)?-1:ans);
	return 0;
}