食物链

题号：NC244187
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

众所周知，MeUmy 大草原有一种神奇的食物链 "羊吃狼(狗)"。终于有一天，可怜的小狼(狗)受不了羊的欺压，决定奋起反抗。但是它肯定打不过羊，所以想请你帮它出谋划策。

决赛场地可以被描述为一颗具有 $n$ 块钢板， $n-1$ 条导线的树，钢板上总共隐藏着不少于 $k$ 个小闪电(不会有两个小闪电在一块钢板上)。任意两个小闪电之间都会通过导线和钢板沿最近的路径接通，进而产生一条电流。

每条导线都有一个威力值(可以为负)，如果某一条导线上经过的电流个数为奇数，小狼就会受到导线威力值的打击，如果个数为偶数，导线就不会对小狼产生打击。

现在小狼想知道，在所有可能的小闪电的分布中，它会受到的最大打击值是多少。

作为帮助它的报酬，它会为你唱一首《黑色小狗》。

正式的，该题意为

给定一颗带边权的 $n$ 个点的树 (可以为负) $T$ , 点的标号由 $1$ 到 $n$ . 考虑所有大小不小于 $k$ 的点集 $S$

你需要求出其中 $f(S)$ 的最大值

其中 $f(S)$ 定义为考虑 $S$ 中所有两点之间的路径，其中被经过奇数次的边的权值和

第一行两个数 , 代表  , 
接下来  行 , 每行  ,  ,  , 代表一条从  连向  , 边权为  的双向边

一个数，代表最大值
特别地 ,  时输出 0

示例1

复制

1 0

复制

示例2

复制

复制

选择1 5