【BZOJ2599】[IOI2011]Race

给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.N <= 200000, K <= 1000000

第一行 两个整数 n, k
第二..n行 每行三个整数 表示一条无向边的两端和权值 (注意点的编号从0开始)

一个整数 表示最小边数量 如果不存在这样的路径 输出-1

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int maxn=200010;int to[maxn<<1],next[maxn<<1],val[maxn<<1],dep[maxn],s[maxn],head[maxn],siz[maxn];int vis[maxn],ans[maxn],p[maxn];int n,m,tot,cnt,root,maxx;bool cmp(int a,int b){	return s[a]<s[b];}void add(int a,int b,int c){	to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;}void getroot(int x,int fa){	int i,mx=0;	siz[x]=1;	for(i=head[x];i!=-1;i=next[i])	{		if(to[i]==fa||vis[to[i]])	continue;		getroot(to[i],x);		siz[x]+=siz[to[i]];		mx=max(mx,siz[to[i]]);	}	mx=max(mx,tot-siz[x]);	if(maxx>mx)	root=x,maxx=mx;}void getdep(int x,int fa){	p[++p[0]]=x;	for(int i=head[x];i!=-1;i=next[i])	{		if(to[i]==fa||vis[to[i]])	continue;		s[to[i]]=s[x]+val[i],dep[to[i]]=dep[x]+1;		getdep(to[i],x);	}}void calc(int x,int flag){	p[0]=0,getdep(x,0);	sort(p+1,p+p[0]+1,cmp);	int l=1,r=p[0],i;	for(;l<r;l++)	{		while(l<r&&s[p[l]]+s[p[r]]>m)	r--;		for(i=r;i>l&&s[p[l]]+s[p[i]]==m;i--)	ans[dep[p[l]]+dep[p[i]]]+=flag;	}}void dfs(int x){	vis[x]=1;	s[x]=dep[x]=0,calc(x,1);	for(int i=head[x];i!=-1;i=next[i])	{		if(vis[to[i]])	continue;		s[to[i]]=val[i],dep[to[i]]=1,calc(to[i],-1);		maxx=1<<30,tot=siz[to[i]],getroot(to[i],x);		dfs(root);	}}int main(){	scanf("%d%d",&n,&m);	int i,a,b,c;	memset(head,-1,sizeof(head));	for(i=1;i<n;i++)	{		scanf("%d%d%d",&a,&b,&c),a++,b++;		add(a,b,c),add(b,a,c);	}	maxx=1<<30;	getroot(1,0);	dfs(1);	for(i=1;i<=n;i++)	{		if(ans[i])		{			printf("%d\n",i);			return 0;		}	}	printf("-1");	return 0;}