http://www.lydsy.com/JudgeOnline/problem.php?id=2599

就是開一個數組t,t[i]表示權值為i的路徑最少邊數

點分治，找到樹的重心分成若干子樹后，

得出一棵子樹的所有點到根的路徑長度x，到根有a條邊，用t[k-x]+a更新答案，

全部查詢完后，然后再用所有a更新t[x]

把一棵樹的所有子樹搞完后再遍歷所有子樹恢復原來t數組

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<map> #include<algorithm> #define FOR(i,s,t) for(register int i=s;i<=t;++i) using namespace std; const int M=400011,N=200011,MAX=1000011,inf=1e9; inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } int n,K,cnt,sum,root,ans; int t[MAX],last[N],son[N],f[N],dis[N],d[N]; bool vis[N]; struct edge{int to,next,v;}e[M]; inline void insert(int u,int v,int w){e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w; } inline void getroot(int x,int fa){son[x]=1;f[x]=0;for(register int i=last[x];i;i=e[i].next)if(e[i].to!=fa&&!vis[e[i].to]){getroot(e[i].to,x);son[x]+=son[e[i].to];f[x]=max(f[x],son[e[i].to]);}f[x]=max(f[x],sum-son[x]);if(f[x]<f[root])root=x; } inline void cal(int x,int fa){if(dis[x]>K)return;ans=min(ans,d[x]+t[K-dis[x]]);for(register int i=last[x];i;i=e[i].next)if(e[i].to!=fa&&!vis[e[i].to]){d[e[i].to]=d[x]+1;dis[e[i].to]=dis[x]+e[i].v;cal(e[i].to,x);} } inline void add(int x,int fa,bool flag){if(dis[x]>K)return;if(flag)t[dis[x]]=min(t[dis[x]],d[x]);else t[dis[x]]=inf;for(register int i=last[x];i;i=e[i].next)if(e[i].to!=fa&&!vis[e[i].to])add(e[i].to,x,flag); } inline void work(int x){vis[x]=1;t[0]=0;for(register int i=last[x];i;i=e[i].next)if(!vis[e[i].to]){d[e[i].to]=1;dis[e[i].to]=e[i].v;cal(e[i].to,0);add(e[i].to,0,1);}for(register int i=last[x];i;i=e[i].next)if(!vis[e[i].to])add(e[i].to,0,0);for(register int i=last[x];i;i=e[i].next)if(!vis[e[i].to]){root=0;sum=son[e[i].to];getroot(e[i].to,0);work(root);} } int u,v,w; int main(){n=read();K=read();FOR(i,1,K)t[i]=n;FOR(i,2,n){u=read(),v=read(),w=read();++u;++v;insert(u,v,w);}ans=sum=f[0]=n;getroot(1,0);work(root);ans!=n?printf("%d\n",ans):puts("-1");return 0; }

　　

轉載于:https://www.cnblogs.com/Stump/p/7979105.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的BZOJ 2599的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。