[IOI2011]Race

题目

题目描述

给一棵树，每条边有权。求一条简单路径，权值和等于$K$，且边的数量最小。

输入输出格式

输入格式：

第一行：两个整数$n,k$。

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

输出格式：

一个整数，表示最小边数量。

如果不存在这样的路径，输出$-1$。

输入输出样例

输入样例#1：

输出样例#1：

说明

$n\leq 200000,K\leq 1000000$。

题解

你会不会淀粉质啊？你学了个假的淀粉质吧，真丢人你褪裙退群吧 ————来着Aufun的嘲讽Orz

找路径长度为$k$，肯定用点分治搞

我的思路是找出所有的$k$长路径，随便记录边数最小值

记录点到根的距离时随便记录点到根的边数

在二分判断是否可行就行了

判断$-1$直接记录树中是否有小于等于$k$的路径

然后得了$80$……

冷静分析，发现判断不了两条边在同一子树里的情况

于是把每棵子树染色，判断边的时候判断是否不在同一子树里

然后……$75$？

奥忘清零了QAQ

然后发现处理不了链的情况，发现判断时出现相同长度的边就可能漏过答案

于是加了个枚举，枚举相同长度的边

终于AC了……复杂度应该比正常做法大一点枚举，开$O2$跑了$5s$多

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=2e5+1;
struct p{
	int x,y,dis;
}c[MAX<<1];
struct q{
	int x,d,id;
	bool operator< (const q &a)
	const{
		if(x!=a.x) return x<a.x;
		return d<a.d;
	}
}d[MAX];
int n,num,cnt,k,rt,Siz,ans,Ans=1e9;
int h[MAX],siz[MAX],f[MAX],id[MAX],sum[MAX];
bool use[MAX];
int read()
{
	int x=0;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x;
}
void add(int x,int y,int dis)
{
	c[++num]=(p){h[x],y,dis},h[x]=num;
	c[++num]=(p){h[y],x,dis},h[y]=num;
}
int max(int x,int y)
{
	return x>y?x:y;
}
int look(int l,int x)
{
	int ans=0,r=cnt;
	while(l<=r)
	{
		int mid(l+r>>1);
		if(d[mid].x<x) l=mid+1;
		else ans=mid,r=mid-1;
	}
	return ans;
}
int look2(int l,int x)
{
	int ans=0,r=cnt;
	while(l<=r)
	{
		int mid(l+r>>1);
		if(d[mid].x<=x) ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
}
void GET_NUM(int x,int fa,int D,int d1)
{
	for(int i=h[x];i;i=c[i].x)
	  {
	  	int y=c[i].y;
	  	if( y == fa || use[y] ) continue;
	  	d[++cnt]=(q){D+c[i].dis,d1+1,y};
	  	if(fa) id[y]=id[x];
	  	GET_NUM(y,x,d[cnt].x,d[cnt].d);
	  }
}
int GET_ANS(int x,int D,int d1)
{
	d[cnt=1]=(q){D,d1,x};
	int col=0;
	id[x]=0;
	for(int i=h[x];i;i=c[i].x)
	  {
	  	int y=c[i].y;
	  	if(use[y]||use[y]) continue;
	  	id[y]=++col;
	  }
	GET_NUM(x,0,D,d1);
	sort(d+1,d+1+cnt);
	int l=1,ans=0;
	while(d[l].x+d[cnt].x<k&&l<cnt) ++l;
	while(l<cnt&&k-d[l].x>=d[l].x)
	{
		int D3,D1(look(l+1,k-d[l].x)),D2(look2(l+1,k-d[l].x));
		D3=D1; 
		for(;id[d[D3].id]==id[d[l].id]&&D3<=cnt;++D3)
		  if(d[D3].x!=k-d[l].x) break;
		if(!D&&d[D3].x==k-d[l].x)
		{
			if(id[d[l].id]!=id[d[D3].id])
			Ans=min(Ans,d[l].d+d[D3].d);
		}
		if(D2>=D1) ans+=D2-D1+1;
		++l;
	}
	return ans;
}
void GET_ROOT(int x,int fa)
{
	siz[x]=1,f[x]=0;
	for(int i=h[x];i;i=c[i].x)
	  {
	  	int y=c[i].y;
	  	if(y==fa||use[y]) continue;
	  	GET_ROOT(y,x);
	  	siz[x]+=siz[y],f[x]=max(f[x],siz[y]);
	  }
	f[x]=max(f[x],Siz-siz[x]);
	if(f[x]<f[rt]) rt=x;
}
void dfs(int x)
{
	use[x]=1,ans+=GET_ANS(x,0,0);
	for(int i=h[x];i;i=c[i].x)
	  {
	  	int y=c[i].y;
	  	if(use[y]) continue;
	  	ans-=GET_ANS(y,c[i].dis,1);
	  	Siz=siz[y],rt=0;
	  	GET_ROOT(y,x),dfs(rt);
	  }
}
int main()
{
	n=read(),k=read();
	for(int i=1;i<n;++i)
	  {
	  	int x=read()+1,y=read()+1,dis=read();
	  	add(x,y,dis);sum[i]=sum[i-1]+dis;
	  }
	f[rt]=Siz=n;
	GET_ROOT(1,0),dfs(1);
	printf("%d",ans?Ans:-1);
	return 0;
}

题目