链接:https://ac.nowcoder.com/acm/contest/4462/B
来源:牛客网

题目描述

给定一棵树 T ,树 T 上每个点都有一个权值。 定义一颗树的子链的大小为:这个子链上所有结点的权值和 。 请在树 T 中找出一条最大的子链并输出。

输入描述:

输出描述:

示例1

输入

输出

说明

备注:

两次dfs:一个大佬证明了先从随意一个点遍历,找到一条最大的路,然后再从路的终点往上找最大路,便是答案。。。。改成long long就过了。。我以后还是习惯longlong吧

树形dp:最长链+次长链。或者答案就是最长链

最后修改日期:2020年2月24日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。