很好的一道treedp,当然也挺烦的
首先不难想到先求出一个直径,然后穷举每条边,看他删除之后直径大小是否会变,变了的话就是必须经过的边
下面我们就要想怎么优化,本人语言表达略差,还是配合程序说吧。

 type node=record
point,next:longint;
cost:int64;
end; var f:array[..] of int64;
pr,fr:array[..,..] of longint;
g,h:array[..,..] of int64;
p:array[..] of longint;
edge:array[..] of node;
v:array[..] of boolean;
i,n,len,ans,x,y,z:longint; procedure add(x,y,z:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].cost:=z;
edge[len].next:=p[x];
p[x]:=len;
end; function max(a,b:int64):int64;
begin
if a>b then exit(a) else exit(b);
end; procedure dp(x:longint);
var i,y:longint;
begin
i:=p[x];
v[x]:=true;
while i<>- do
begin
y:=edge[i].point;
if not v[y] then
begin
dp(y);
f[x]:=max(f[x],f[y]); //f[]表示以x为根的子树中最长的路径长
if g[y,]+edge[i].cost>g[x,] then //维护以x为根走到底最长的3条路径(显然不能有两条路径经过同一个孩子)
//这里要维护3条,因为要考虑删边的时候碰巧干掉了其中一条,如果单纯求树的直径的时候只要维护最长和次长即可)
begin
g[x,]:=g[x,];
fr[x,]:=fr[x,];
g[x,]:=g[x,];
fr[x,]:=fr[x,];
g[x,]:=g[y,]+edge[i].cost;
fr[x,]:=y; //从哪转移来的
end
else if (g[y,]+edge[i].cost>g[x,]) then
begin
g[x,]:=g[x,];
fr[x,]:=fr[x,];
g[x,]:=g[y,]+edge[i].cost;
fr[x,]:=y;
end
else if (g[y,]+edge[i].cost>g[x,]) then
begin
g[x,]:=g[y,]+edge[i].cost;
fr[x,]:=y;
end;
if f[y]>h[x,] then //h维护的是以x为根的子树中最长的2条路径(不经过根)
begin
h[x,]:=h[x,];
pr[x,]:=pr[x,];
h[x,]:=f[y];
pr[x,]:=y; //从哪转移来的
end
else if f[y]>h[x,] then
begin
h[x,]:=f[y];
pr[x,]:=y;
end;
end;
i:=edge[i].next;
end;
f[x]:=max(f[x],g[x,]+g[x,]);
end; procedure dfs(x:longint;l,d:int64); //l表示以x为终点且不是起点x的后辈的最长路径,d表示之前搜索到的不经过x的最长路径
var i,y:longint;
l1,l2,l3:int64;
begin
i:=p[x];
v[x]:=true;
while i<>- do
begin
y:=edge[i].point;
if not v[y] then //大批的分类讨论
begin
l1:=f[y];
if y=pr[x,] then l2:=h[x,]
else l2:=h[x,];
l2:=max(l2,d); if y=fr[x,] then l2:=max(l2,g[x,]+g[x,])
else if y=fr[x,] then l2:=max(l2,g[x,]+g[x,])
else l2:=max(l2,g[x,]+g[x,]); if y=fr[x,] then l3:=g[x,]
else l3:=g[x,];
l2:=max(l2,l+l3);
if max(l1,l2)<f[] then inc(ans);
dfs(y,max(l3,l)+edge[i].cost,l2);
end;
i:=edge[i].next;
end;
end; begin
readln(n);
fillchar(p,sizeof(p),);
for i:= to n- do
begin
readln(x,y,z);
add(x,y,z);
add(y,x,z);
end;
dp();
writeln(f[]);
fillchar(v,sizeof(v),false);
ans:=;
dfs(,,);
writeln(ans);
end.

最新文章

  1. PHP反向代理-百度图片
  2. 2017年1月4日-linux学习
  3. JavaScript对UNIX时间戳的转换
  4. 【C#】第2章学习要点
  5. 利用Jmeter进行Web测试
  6. myEclipse
  7. UI组件(思维导图)
  8. 蓝牙音箱bose soundlink mini2链接mac后itunes自动启动的问题解决
  9. SAP BAPI创建批次 为保存内部对象号
  10. windows下用pip安装软件超时解决方案
  11. Flex中获取RadioButtonGroup中的RadioButton的值
  12. #20175204 张湲祯 2018-2019-2《Java程序设计》第五周学习总结
  13. Redis 设计与实现 (六)--发布订阅
  14. chocolatey使用
  15. 人只能靠自己 编写ETL框架使用工具
  16. 推荐使用@Resource,不推荐使用@Autowired
  17. GRE封装解封装过程
  18. unsafe关键字
  19. flowable学习笔记-简单流程概念介绍
  20. Tomcat上发布webservices的war工程,访问异常404

热门文章

  1. PLSQL Developer操作
  2. 学习java随笔第九篇:java异常处理
  3. [XML] resources的Xml配置文件 (转载)
  4. SQL Execute语法.
  5. matlab中max的用法
  6. 使用methodSignatureForSelector与forwardInvocation实现消息转发 (转)
  7. 自然数e为底数的指数函数的一个小运用
  8. MFC中cannot find the definition (implementation) of this function 解决方法
  9. 自己使用Jquery封装各种功能分享
  10. c++builder调用vc的dll