{"problem":{"name":"[PA 2021] Poborcy podatkowi","description":{"content":"给定一棵 $n$ 个点的树，你可以选择若干条长度为 $4$（指 $4$ 条边） 的不相交链（**可以不选**）。 每个选链的方案的收益为所选链的并集的边权和，求最大收益。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":7000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9047"},"statements":[{"statement_type":"Markdown","content":"给定一棵 $n$ 个点的树，你可以选择若干条长度为 $4$（指 $4$ 条边） 的不相交链（**可以不选**）。\n\n每个选链的方案的收益为所选链的并集的边权和，求最大收益。\n\n## Input\n\n第一行，一个整数 $n$；\n\n接下来 $n - 1$ 行，每行三个整数 $u, v, w$，表示树上的一条边 $(u, v)$，其边权为 $w$。\n\n## Output\n\n一行，一个整数，表示所求的值。\n\n[samples]\n\n## Note\n\n#### 样例 #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$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9047","tags":["动态规划 DP","2021","分治","剪枝","背包 DP","动态规划优化","树形 DP","凸完全单调性（wqs 二分）","随机化","PA（波兰）"],"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"]],"created_at":"2026-03-03 11:09:25"}}