思路： 点分治
提交：5次
题解：
刚开始用排序+双指针写的，但是调了一晚上，总是有两个点过不了，第二天发现原因是排序时的(cmp)函数写错了：如果对于路径长度相同的，我们从小往大按边数排序，当双指针出现(==k)时，即我们应先左移右指针，否则答案可能会变劣（仔细想一想）；若反着排序，应该先右移左指针。
#include<bits/stdc++.h>
#define R register int
using namespace std;
namespace Luitaryi {
template<class I> inline I g(I& x) { x=0; register I f=1;
register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;
do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*=f;
} const int N=2e5+10,Inf=1e+9;
int n,K,cnt,sum,rt,tot,ans=N; bool vis[N];
int vr[N<<1],nxt[N<<1],fir[N],w[N<<1],sz[N],d[N],f[N],b[N],mx[N],mem[N];
inline void add(int u,int v,int ww) {
vr[++cnt]=v,nxt[cnt]=fir[u],w[cnt]=ww,fir[u]=cnt;
vr[++cnt]=u,nxt[cnt]=fir[v],w[cnt]=ww,fir[v]=cnt;
}
inline void getsz(int u,int fa) { sz[u]=1,mx[u]=0;
for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
if(v==fa||vis[v]) continue;
getsz(v,u),sz[u]+=sz[v];
mx[u]=max(mx[u],sz[v]);
} mx[u]=max(mx[u],sum-sz[u]);
if(mx[u]<mx[rt]) rt=u;
}
inline void getdis(int u,int fa) { mem[++tot]=u;
for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
if(v==fa||vis[v]) continue;
d[v]=d[u]+w[i],f[v]=f[u]+1,b[v]=b[u];
if(d[v]<=K) getdis(v,u);
}
}
inline bool cmp(const int& a,const int& b) {
return d[a]<d[b]||(d[a]==d[b]&&f[a]>f[b]);
}
inline void solve(int u,int fa) {
tot=0,vis[u]=true; mem[++tot]=u,d[u]=f[u]=0,b[u]=u;
for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
if(v==fa||vis[v]) continue;
d[v]=w[i],f[v]=1,b[v]=v; getdis(v,u);
} sort(mem+1,mem+tot+1,cmp);
// for(R i=1;i<=tot;++i) cout<<mem[i]<<" "; cout<<endl;
R l=1,r=tot; while(l<r) {
if(d[mem[l]]+d[mem[r]]>K) --r;
else if(d[mem[l]]+d[mem[r]]<K) ++l;
else if(b[mem[l]]==b[mem[r]]) {
// if(d[mem[r]]==d[mem[r-1]]) --r;
// else ++l;
if(d[mem[l]]==d[mem[l+1]]) ++l;
else --r;
} else {
ans=min(ans,f[mem[l]]+f[mem[r]]);
// if(d[mem[r]]==d[mem[r-1]]) --r;
// else ++l;
if(d[mem[l]]==d[mem[l+1]]) ++l;
else --r;
}
} for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
if(v==fa||vis[v]) continue;
sum=sz[v],rt=0,mx[rt]=Inf;
getsz(v,u); getsz(rt,-1); solve(rt,u);
}
}
inline void main() {
g(n),g(K); for(R i=1,u,v,w;i<n;++i) g(u),g(v),g(w),++u,++v,add(u,v,w);
sum=n,mx[0]=Inf; getsz(1,-1),getsz(rt,-1); solve(rt,-1);
if(ans==N) return (void) puts("-1"); printf("%d
",ans);
}
} signed main() {Luitaryi::main(); return 0;}
但是上面的方法比较慢，多一个(log)。
于是还是类比点分治板子的思想，对于一颗子树，与之前的子树做贡献。我们可以开一个类似桶的数组记录长度为(len)的路径有没有出现过，同时对应记录长度为(len)的路径对应的最小边数。每求出来一颗子树的信息就扫一遍。
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define R register int
using namespace std;
namespace Luitaryi {
template<class I> inline I g(I& x) { x=0; register I f=1;
register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;
do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*=f;
} const int N=2e5+10,M=1e6+10,Inf=0x3f3f3f3f;
int n,K,cnt,sum,rt,tot,ans=N,SZ; bool vis[N],mem[M];
int vr[N<<1],nxt[N<<1],fir[N],w[N<<1],sz[N],d[N],f[M],s[N],mx[N],buf[N],l[N],dis[N];
inline void add(int u,int v,int ww) {
vr[++cnt]=v,nxt[cnt]=fir[u],w[cnt]=ww,fir[u]=cnt;
vr[++cnt]=u,nxt[cnt]=fir[v],w[cnt]=ww,fir[v]=cnt;
}
inline void getsz(int u,int fa) { sz[u]=1,mx[u]=0;
for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
if(v==fa||vis[v]) continue;
getsz(v,u),sz[u]+=sz[v];
mx[u]=max(mx[u],sz[v]);
} mx[u]=max(mx[u],sum-sz[u]);
if(mx[u]<mx[rt]) rt=u;
}
inline void getdis(int u,int fa) {
dis[++tot]=d[u],l[tot]=s[u];
for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
if(v==fa||vis[v]) continue;
d[v]=d[u]+w[i],s[v]=s[u]+1;
if(d[v]<=K) getdis(v,u);
}
}
//inline bool cmp(const int& a,const int& b) {
// return d[a]<d[b]||(d[a]==d[b]&&f[a]>f[b]);
//}
//inline void solve(int u,int fa) {
// tot=0,vis[u]=true; mem[++tot]=u,d[u]=f[u]=0,b[u]=u;
// for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
// if(v==fa||vis[v]) continue;
// d[v]=w[i],f[v]=1,b[v]=v; getdis(v,u);
// } sort(mem+1,mem+tot+1,cmp);
//// for(R i=1;i<=tot;++i) cout<<mem[i]<<" "; cout<<endl;
// R l=1,r=tot; while(l<r) {
// if(d[mem[l]]+d[mem[r]]>K) --r;
// else if(d[mem[l]]+d[mem[r]]<K) ++l;
// else if(b[mem[l]]==b[mem[r]]) {
//// if(d[mem[r]]==d[mem[r-1]]) --r;
//// else ++l;
// if(d[mem[l]]==d[mem[l+1]]) ++l;
// else --r;
// } else {
// ans=min(ans,f[mem[l]]+f[mem[r]]);
//// if(d[mem[r]]==d[mem[r-1]]) --r;
//// else ++l;
// if(d[mem[l]]==d[mem[l+1]]) ++l;
// else --r;
// }
// } for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
// if(v==fa||vis[v]) continue;
// sum=sz[v],rt=0,mx[rt]=Inf;
// getsz(v,u); getsz(rt,-1); solve(rt,u);
// }
//}
inline void solve(int u,int fa) { tot=0; vis[u]=true;
buf[++SZ]=0,mem[0]=true,d[u]=s[u]=0,f[0]=0;
for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
if(vis[v]||v==fa) continue;
d[v]=w[i],s[v]=1; getdis(v,u);
for(R i=1;i<=tot;++i) if(K>=dis[i]&&mem[K-dis[i]])
ans=min(ans,f[K-dis[i]]+l[i]);
for(R i=1;i<=tot;++i) {
if(!mem[dis[i]]) buf[++SZ]=dis[i],mem[dis[i]]=true;
f[dis[i]]=min(f[dis[i]],l[i]);
} tot=0;
} while(SZ) mem[buf[SZ]]=false,f[buf[SZ]]=Inf,--SZ;
for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
if(v==fa||vis[v]) continue;
sum=sz[v],rt=0,mx[rt]=Inf;
getsz(v,u),getsz(rt,-1); solve(rt,u);
}
}
inline void main() {
memset(f,0x3f,sizeof(f)); g(n),g(K);
for(R i=1,u,v,w;i<n;++i) g(u),g(v),g(w),++u,++v,add(u,v,w);
sum=n,mx[0]=Inf; getsz(1,-1),getsz(rt,-1); solve(rt,-1);
if(ans==N) return (void) puts("-1"); printf("%d
",ans);
}
} signed main() {Luitaryi::main(); return 0;}
还有最近老犯一个错误，数组名老弄重导致算错。。。必须给予重视。。
2019.08.31
69