题意:给定一棵有边权的树 和一个k 问最少多少边（连续)的长度和为k
解法一（也是我一开始的写法)
遍历所有的边 并且给每个边设置一个标记属于某课子树 然后用lowerbound和upperbound找到满足的边 遍历一遍统计答案 用了4s
解法二（只用2s）
边数太多的时候上面的算法复杂度接近 n^2logn QAQ
可以做成3n的 并且每一棵每一棵子树得统计答案和更新子树情况 （先统计 后更新) 就可以避免统计的边不是最短路的情况
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////////// const int N=2e5+10; int n,m,cnt,d[N],head[N],pos,siz[N],sum,x,y,z,ans,vis[N],root,maxson[N],k,temp[N*10]; struct Edge{int to,nex,v;}edge[N<<1]; void add(int a,int b,int c){edge[++pos]=(Edge){b,head[a],c};head[a]=pos;} struct bian { int num,v,belong; bool operator <(const bian &b)const{return v<b.v;} }s[N]; void getroot(int x,int fa) { siz[x]=1;maxson[x]=0; for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to; if(vis[v]||v==fa)continue; getroot(v,x);siz[x]+=siz[v]; maxson[x]=max(maxson[x],siz[v]); } maxson[x]=max(maxson[x],sum-siz[x]); if(maxson[x]<maxson[root])root=x; } void getdis(int x,int fa,int val,int num) { if(val>k)return ; temp[val]=min(temp[val],num); for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to; if(vis[v]||v==fa)continue; getdis(v,x,val+edge[i].v,num+1); } } void init(int x,int fa,int val) { if(val>k)return ; temp[val]=1e9 ; for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to; if(vis[v]||v==fa)continue; init(v,x,edge[i].v+val); } } void upans(int x,int fa,int val,int num) { if(val>k)return ; ans=min(ans,temp[k-val]+num); for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to; if(vis[v]||v==fa)continue; upans(v,x,val+edge[i].v,num+1); } } void calc(int x) { temp[0]=0; for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to; if(vis[v])continue; upans(v,x,edge[i].v,1); getdis(v,x,edge[i].v,1); } init(x,0,0); } void solve(int x) { vis[x]=1; calc(x); for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to; if(vis[v])continue; root=0;sum=siz[v]; getroot(v,x); solve(root); } } int main() { scanf("%d%d",&n,&k); rep(i,1,n-1) scanf("%d%d%d",&x,&y,&z),x++,y++,add(x,y,z),add(y,x,z); rep(i,0,k)temp[i]=1e9; ans=1e9; sum=maxson[0]=n; root=0; getroot(1,0); solve(root); if(ans==1e9)printf("-1 "); else printf("%d",ans); }