Description
给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.N <= 200000, K <= 1000000
Input
第一行 两个整数 n, k 第二..n行 每行三个整数 表示一条无向边的两端和权值 (注意点的编号从0开始)
Output
一个整数 表示最小边数量 如果不存在这样的路径 输出-1
Sample Input
4 3
0 1 1
1 2 2
1 3 4
Sample Output
2
HINT
2018.1.3新加数据一组，未重测
题解
很明显的点分
设li[i][0]/li[i][1]分别表示到当前根长度为i的路径最短/次短的两条，并强制要求这两条路径来自不同子树。优先考虑最短其次次短
由于每次只会有比上一次少一半的点做出贡献，所以复杂度是 O(nlogn) O ( n log ? n )
打个时间戳回收一下数组
然后就可以很愉快地点分啦
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
struct po{
int s,fro;}w[210000];int ln;
struct list{
int c,fro,tim;}li[1110000][2];int ti,n,m;
//pt divide
struct node{
int x,y,c,next;}a[410000];int len,last[210000];
void ins(int x,int y,int c){len++;a[len].x=x;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;}
int f[210000],tot[210000],G,sum;
bool v[210000];
void getrt(int x,int fa)
{tot[x]=1;f[x]=0;for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(y!=fa && !v[y]){getrt(y,x);f[x]=max(f[x],tot[y]);tot[x]+=tot[y];}}f[x]=max(f[x],sum-tot[x]);if(f[G]>f[x])G=x;
}
void dfs(int x,int fa,int dis,int e,int fro)
{if(dis<=m){ln++;w[ln].s=dis;w[ln].fro=fro;if(e<li[dis][0].c || li[dis][0].tim!=ti){list tmp=li[dis][0];li[dis][0].c=e;li[dis][0].fro=fro;li[dis][0].tim=ti;if(tmp.tim==ti && tmp.fro!=fro){if(li[dis][1].c>=tmp.c || li[dis][1].tim!=ti)li[dis][1]=tmp;}}else if((e<li[dis][1].c|| li[dis][1].tim!=ti) && li[dis][0].fro!=fro)li[dis][1].c=e,li[dis][1].fro=fro,li[dis][1].tim=ti;}else return ;for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(y!=fa && !v[y])dfs(y,x,dis+a[k].c,e+1,fro);}
}
int ans;
void getans()
{int ss=999999999;for(int j=1;j<=ln;j++){int i=w[j].s;if(li[i][0].tim==ti && li[m-i][0].tim==ti){int e=999999999;if(li[i][0].fro!=li[m-i][0].fro)e=li[i][0].c+li[m-i][0].c;if(li[i][0].fro!=li[m-i][1].fro && li[m-i][1].tim==ti)e=min(e,li[i][0].c+li[m-i][1].c);if(li[i][1].fro!=li[m-i][0].fro && li[i][1].tim==ti)e=min(e,li[i][1].c+li[m-i][0].c);if(li[i][1].fro!=li[m-i][1].fro && li[m-i][1].tim==ti && li[i][1].tim==ti)e=min(e,li[i][1].c+li[m-i][1].c);ss=min(ss,e);}}if(li[m][0].tim==ti)ans=min(ans,li[m][0].c);ans=min(ans,ss);
}
void sol(int x)
{v[x]=true;ti++;ln=0;for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(!v[y])dfs(y,x,a[k].c,1,y);}getans();for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(!v[y]){G=0;sum=tot[y];getrt(y,x);sol(G);}}
}
int main()
{scanf("%d%d",&n,&m);len=0;memset(last,0,sizeof(last));for(int i=1;i<n;i++){int x,y,c;scanf("%d%d%d",&x,&y,&c);x++;y++;ins(x,y,c);ins(y,x,c);}memset(v,false,sizeof(v));f[0]=999999999;G=0;sum=n;getrt(1,0);ans=999999999;sol(G);if(ans!=999999999)printf("%d\n",ans);else printf("-1\n");return 0;
}