{"raw_statement":[{"iden":"statement","content":"给定一棵 $n$ 个点的树，你可以选择若干条长度为 $4$（指 $4$ 条边） 的不相交链（**可以不选**）。\n\n每个选链的方案的收益为所选链的并集的边权和，求最大收益。"},{"iden":"input","content":"第一行，一个整数 $n$；\n\n接下来 $n - 1$ 行，每行三个整数 $u, v, w$，表示树上的一条边 $(u, v)$，其边权为 $w$。"},{"iden":"output","content":"一行，一个整数，表示所求的值。"},{"iden":"note","content":"#### 样例 #1 解释\n给出一种最优方案：选择链 $2 \\to 6$，$6 \\to 10$，$11 \\to 15$，$16 \\to 19$。\n#### 样例 #2 解释\n由于每一条长度为 $4$ 的链权值均为负数，所以不选最优。\n#### 数据范围\n对于 $100\\%$ 的数据，$2 \\leq n \\leq 2 \\times 10^5$，$-10^9 \\leq w_i \\leq 10^9$。"}],"translated_statement":null,"sample_group":[["19\n1 2 1\n2 3 2\n3 4 -1\n4 5 -1\n5 6 2\n6 7 11\n7 8 12\n8 9 13\n9 10 14\n11 12 3\n12 13 0\n13 14 0\n14 15 0\n15 16 1\n16 4 0\n4 17 0\n17 18 0\n18 19 2","57"],["6\n1 2 2\n2 3 -1\n3 4 -1\n4 5 -1\n5 6 2","0"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}