luogu#P11259. [GDKOI2023 普及组] 海星
[GDKOI2023 普及组] 海星
题目描述
小明想去海底抓海星, 海底是一个树状的结构,而海星就藏在里面。
给定一棵 个点的树,分别标号为 , 且对应的点权记为 。
定义海星为其中的花子图,不妨设其中心节点标号为 , 边缘节点标号为 (其中边缘节点必 定直接与中心节点相连,同时花子图至少由一个中心节点和一个边缘节点构成)。此时记海星的价值为 。
小明想知道他最多能抓到价值总和为多少的海星。(可以同时抓很多只海星,但是任意两个海星之间点的 交集必须为空)
补充定义:
花图: 直径小于等于三的联通图,其中度数最大的节点为中心节点,其余节点为边缘节点(可知任意的边 缘节点度数为一)
示例:最小的花图,是 ,仅由两个节点和联结它们的一条边构成。
输入格式
第一行,一个正整数 ,表示树的大小;
第 行, 个整数,表示 ;
第 行,每行 个整数 ,分别表示 号节点与 号节点之间有一条边。
输出格式
一行,一个整数,表示小明能抓到的最大海星的价值总和。
5
-2 -3 4 -5 1
1 2
1 3
2 4
2 5
10
见/example/starfish/下
见/example/starfish/下
提示
样例解释
一个合法的方案是,小明抓了两个海星,第一个海星的中心节点为 ,边缘节点为 ,价值为 ;第二个 海星的中心节点为 ,边缘节点为 ,价值为 ,此时得到最大总价值 。
数据范围
对于 的数据,保证数据形成一个花图。
对于 的数据,保证数据形成一条链。
对于 的数据,保证数据相邻节点乘积恒负。
对于 的数据,保证数据形成一颗以 1 为根节点的二叉树。
对于 的数据,无特殊限制。
对于所有数据 ,。
下发样例中编号为 的数据对应序号为 的限制条件. 。