点分治裸题

#include<iostream>
#include<cstring>
#include<cstdio> using namespace std; inline int rd(){
int ret=,f=;char c;
while(c=getchar(),!isdigit(c))f=c=='-'?-:;
while(isdigit(c))ret=ret*+c-'',c=getchar();
return ret*f;
} const int MAXN=; struct Edge{
int next,to,w;
}e[MAXN<<];
int ecnt,head[MAXN];
inline void add(int x,int y,int w){
e[++ecnt].next = head[x];
e[ecnt].to = y;
e[ecnt].w = w;
head[x] = ecnt;
} int n,m; bool vis[MAXN];
int siz[MAXN];
void getsiz(int x,int pre){
siz[x]=;
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(v==pre||vis[v]) continue;
getsiz(v,x);
siz[x]+=siz[v];
}
}
int mn,root;
void getroot(int x,int pre,int tot){
int mx=;
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(v==pre||vis[v]) continue;
mx=max(mx,siz[v]);
getroot(v,x,tot);
}
mx=max(mx,tot-siz[x]);
if(mx<mn) mn=mx,root=x;
} int s[MAXN],l[MAXN],sav[MAXN];
int f[],g[];
void dfs(int x,int pre,int dis,int len){
s[++s[]]=dis;l[++l[]]=len;sav[++sav[]]=dis;
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(vis[v]||v==pre) continue;
dfs(v,x,dis+e[i].w,len+);
}
} int ans=0x3f3f3f3f;
void dac(int x){
g[]=;f[]=;sav[]=;mn=n;
getsiz(x,-);
getroot(x,-,siz[x]);
int u=root;vis[u]=;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(vis[v]) continue;
l[]=;s[]=;dfs(v,x,e[i].w,);
for(int j=s[];j>=;j--){
if(s[j]>m) continue;
if(f[m-s[j]]) ans=min(ans,g[m-s[j]]+l[j]);
}
for(int j=s[];j>=;j--){
if(s[j]>m) continue;//%%%%Monster_Qi
f[s[j]]=;
g[s[j]]=min(g[s[j]],l[j]);
}
}
for(int i=sav[];i>=;i--) if(sav[i]<=m) f[sav[i]]=,g[sav[i]]=0x3f3f3f3f;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(!vis[v]) dac(v);
}
} int main(){
memset(g,0x3f,sizeof(g));
n=rd();m=rd();
int x,y,w;
for(int i=;i<n;i++){
x=rd();y=rd();w=rd();
add(x,y,w);add(y,x,w);
}
dac();
if(ans>=0x3f3f3f3f) cout<<-;
else cout<<ans;
return ;
}

最新文章

  1. ubuntu14.04下安装node.js
  2. bzoj4025 二分图
  3. 十三. JEB破解三
  4. freecodecamp记录
  5. linux如何编译安装新内核支持NTFS文件系统?(以redhat7.2x64为例)
  6. XE8 for iOS 状态栏的几种效果
  7. AjaxFormSubmit使用demo
  8. KMP算法的Next数组详解
  9. ProcDump
  10. HDU 4160
  11. POJ 3045
  12. 无需安装Mono的Jexus
  13. java入门学习笔记之2(Java中的字符串操作)
  14. github 管理代码: code.Aliyun
  15. CentOS 7 环境下GitLab安装及基本配置
  16. C++——list中erase和remove的区别
  17. Canvas入门到高级详解(中)
  18. s21day10 python笔记
  19. 基于IOS上MDM技术相关资料整理及汇总
  20. python学习疑问

热门文章

  1. Linux —— GDB调试程序
  2. Net Core迁移到MSBuild
  3. 044 Wildcard Matching 通配符匹配
  4. vi命令使用
  5. ruby 字符串常用方法学习
  6. 提升Java代码质量(一)
  7. [Loading Component]Loading组件的v-model设计是否不合理?
  8. html5 03
  9. Android中文件加密和解密的实现
  10. Protocol Buffer学习教程之编译器与类文件(三)