赛时
先上来看T1,发现没有什么性质,所以一定是搜索
然后考虑到n很小,所以直接搜,然后剪枝,就一定能过
大概50分钟左右过了
然后看T2,先想了链和菊花的情况
但是剩下的就想不到了
能想到,大概率是个dp
但是感觉也有可能是贪心,没怎么想
然后就想T3了
T3真的感觉很可做
开始就想到了sb2 meet-in-middle做法
然后想到了sb3 很好做,在做并查集的时候撤销A的贡献即可
然后想sb1 ,想建一个生成树,然后两边分别跑并查集,但是写的时候发现没法撤销两边同时的贡献
然后就想不到了
但其实,这个单调性我是没想到的
考虑到A答案升高,B答案一定不会增大
所以双指针
我们一边合并集合,一边撤销合并集合
考虑怎么容斥掉贡献,考虑到维护C集合,A集合和B集合在同一个集合的点会被存在C同一个集合
给每个A集合和每个B集合给定一个哈希值,然后,HA^HB相同的在同一个C集合中
考虑合并两个集合时,启发式合并,同时把小的那一部分集合拿出来重新贡献
分裂时用log的空间记录一下原先分裂之前的点
T4考场上看了几眼觉得不可做就扔了
赛后
100+25+0+0(T3由于题目细节没有特判,爆0了)
听题目时不知为何,T2和T3就是听不懂(是我很笨么?可能是的)))
最后终于问明白了,没有补
T2核弹做法dp
设到u剩奇链还是偶链还有剩0/1/>=2个儿子
包含了所有能影响答案的情况
然后用树上dp经典的撤销操作,要几个链撤销几个贡献(w-max原先的贡献-现在的贡献)这种的
所有与定义状态冲突的都撤销
T2贪心做法:
考虑到奇数边和偶数边,一定是删少的那个更优,因为代价为1(满足局部最优)
然后考虑一个点儿子奇数点还是偶数点(儿子是根据儿子的删边情况来判断),特殊情况,无法判断(f1=f2)则不产生贡献
不能让叶子当根