【旧事重提】有树焉

WeLikeStudying · 2022-03-12 12:10:33 · 个人记录

题意

• 链接。
• 有树焉，边有权焉，选链异或 x 焉，使其权为 0 焉，最小化其次数焉。

分析

• 令点之权为其边权之异或，则一链止其端点与，无忧其边已，止 15 权与数目焉。
• 贪心先消相等的点，止 32768 种情况已，爆搜即可。
• 巧妙的方法，最暴力的上界是点的个数减 1，这个只考虑当前一个就可以得到，拆分成多个子集异或和为 0，可以更多减少，即一种贪心。
• 代码实现，写出来搞笑的。
• 作者放在这里有两个问题：题目出这个树的性质几乎在糊弄我们（当然如果牵强地说确实也利用了树的性质），我容易理解，但并不能完全理解后面的贪心（虽然但是把图建出来跑最短路也差不多可以）。