题意:

边权可能为负

思路:

感觉我自己写的还是太过僵硬了,可以灵活一点,比如可以多写几个不同的dfs求出不同的信息,而不是压到同一个dfs里

 #include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef vector<int> VI;
#define fi first
#define se second s
#define MP make_pair
#define N 410000
#define M 1100000
#define MOD 1000000007
#define eps 1e-8
#define pi acos(-1)
#define oo 2e9+1 struct node
{
int x,id;
}b[N]; int head[N],vet[N],nxt[N],len[N],dis[N],dep[N],mxdep[N],son[N],flag[N],c[N],a[N],f[N],tmp[N],mx[N],
n,K,tot,top,ans,sum,root; int read()
{
int v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
} bool cmp(node a,node b)
{
return a.x<b.x||
(a.x==b.x&&a.id<b.id); } void add(int a,int b,int c)
{
nxt[++tot]=head[a];
vet[tot]=b;
len[tot]=c;
head[a]=tot;
} void getroot(int u,int fa)
{
son[u]=; c[u]=;
int e=head[u];
while(e)
{
int v=vet[e];
if(v!=fa&&!flag[v])
{
getroot(v,u);
son[u]+=son[v];
c[u]=max(c[u],son[v]);
}
e=nxt[e];
}
c[u]=max(c[u],sum-c[u]);
if(c[u]<c[root]) root=u;
} void dfs(int u,int fa)
{
mxdep[u]=dep[u];
int e=head[u];
while(e)
{
int v=vet[e];
if(v!=fa&&!flag[v])
{
dep[v]=dep[u]+a[v];
dis[v]=dis[u]+len[e];
dfs(v,u);
mxdep[u]=max(mxdep[u],mxdep[v]);
}
e=nxt[e];
}
} void getmx(int u,int fa)
{
tmp[dep[u]]=max(tmp[dep[u]],dis[u]);
int e=head[u];
while(e)
{
int v=vet[e];
if(v!=fa&&!flag[v]) getmx(v,u);
e=nxt[e];
}
} void work(int u)
{
flag[u]=;
f[]=;
if(a[u]) K--;
int m=;
int e=head[u];
while(e)
{
int v=vet[e];
if(!flag[v])
{
top=;
dep[v]=a[v];
dis[v]=len[e];
dfs(v,u);
b[++m].x=mxdep[v];
b[m].id=v;
}
e=nxt[e];
} sort(b+,b+m+,cmp);
for(int i=;i<=m;i++)
{
int v=b[i].id;
getmx(v,u);
int now=;
if(i>)
{
for(int j=b[i].x;j>=;j--)
{
while(now+j<K&&now<b[i-].x)
{
now++;
mx[now]=max(mx[now],mx[now-]);
}
if(now+j<=K) ans=max(ans,mx[now]+tmp[j]);
}
}
if(i<m)
{
for(int j=;j<=b[i].x;j++)
{
mx[j]=max(mx[j],tmp[j]);
tmp[j]=;
}
}
else
{
for(int j=;j<=b[i].x;j++)
{
if(j<=K) ans=max(ans,max(tmp[j],mx[j]));
tmp[j]=mx[j]=;
}
}
} if(a[u]) K++;
e=head[u];
while(e)
{
int v=vet[e];
if(!flag[v])
{
sum=son[v]; root=;
getroot(v,u);
work(root);
}
e=nxt[e];
} } int main()
{
freopen("spoj1825.in","r",stdin);
freopen("spoj1825.out","w",stdout);
int m;
scanf("%d%d%d",&n,&K,&m);
for(int i=;i<=m;i++)
{
int x;
scanf("%d",&x);
a[x]=;
}
for(int i=;i<=n-;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
ans=;
root=; sum=n; c[]=n; getroot(,);
work(root);
printf("%d\n",ans);
return ;
}

最新文章

  1. 随笔分类 - [C#6] 新增特性
  2. VIM使用技巧总结
  3. 关于python文件操作
  4. 结构体的malloc与数组空间
  5. java总结
  6. 带参数的URLconf
  7. PHP -- 添加注释
  8. iOS中Block介绍(二)内存管理与其他特性
  9. JSch - Java实现的SFTP
  10. cesium Animation显示系统时间
  11. vue+element-ui之tree树形控件有关子节点和父节点之间的各种选中关系详解
  12. MFC 对话框不显示,返回-1 原因
  13. 设备 VMnet0 上的网桥当前未运行。此虚拟机无法与主机或网络中的其他计算机通信。
  14. Latex数学公式中的空格
  15. SQL server数据库的部署
  16. 使用开源库 MBProgressHUD 等待指示器
  17. python学习之多线程(二)
  18. Carbon中文使用手册
  19. JDK源码分析:Short.java
  20. Java 如何解析由String类型拼接的XML格式

热门文章

  1. ucosii(2.89)mbox 应用要点
  2. 结合浅层高层特征的paper总结
  3. Python 解压序列、可迭代对象并赋值给多个变量
  4. 14.list列表
  5. EOF与feof
  6. common-fileupload上传文件
  7. python-DB模块
  8. windows 下phpstudy 升级mysql版本5.7
  9. MySQL 上移/下移/置顶
  10. Linux服务器的弱口令检测及端口扫描