《情报中心》
试题讲评
清华大学
陈俊锟 吕欣 杨景钦 王逸松
预谋已久
• 早在 WC 刚结束时，这题已颇具雏形
• 但是当时，我们都并不会做，于是这题被搁置
• 4 月中旬的一天下午，TAC 忽然想出了这题的算法
• 本想把这题投给 CTSC，但惨遭拒绝
• 于是——这题被留到了 NOI！
题意简述
• 给出一棵 𝑛 个点的树，每条边有非负边权
• 再给出 𝑚 条树上的链，用端点表示，每条链都有价值
• 要求选出两条链，满足这两条链至少有一条边相交
• 最大化选出的链的权值和 + 被至少一条链覆盖的边的边权和
• 一个测试点可能有很多组数据，𝑛 ≤ 50,000、𝑚 ≤ 100,000
• 测试点内的 𝑛 和 𝑚 的和的数量级达到 10
6
• 时间限制 8 秒，空间限制 512 MB
得分情况
梗与吐槽
• C 国和 D 国 → 猫（Cat）狗（Dog）大战
• reversed(BGG = 板给给哥哥) 和 reversed(CAT)
• 样例 4 的强度接近终测数据
• std 是一个 log 的
