1 条题解

  • 0
    @ 2026-11-15 21:38:39

    题目分析

    答案 =n−1−=n−1− 交集的最大值。

    对于每条边 ii,假设覆盖它的路径集合是 SiS_i,那么出现次数最多的 SiS_i 的出现次数就是交集的最大值。

    给每条路径随机一个 [0,263)[0,2^{63}) 内的权值,每条边的权值取成覆盖它的路径权值的异或和,利用树上差分即可。

    • 1

    信息

    ID
    206
    时间
    2000ms
    内存
    1024MiB
    难度
    5
    标签
    递交数
    2
    已通过
    1
    上传者