一早上赶紧起来准备设备 到了8:55进到腾讯会议发现笔记本的前置摄像头bz了 赶紧换了另外一台笔记本(所有的板子都没了)
开场先把3题都看了一遍。。。感觉一题都不可做啊
T1
先看T1 不太明白那个 (sum f(i)^2 le 400000) 的意义何在
发现如果知道了对于哪些 (y) 存在合法的染色方案，那么就可以直接进行dp，套一个单调队列就是 (O(n)) 的
一开始写了个set来存对于每一面墙，有哪些染色公司可以染它 然后暴力处理哪些 (y) 有合法染色方案
但是set实在是太慢了 只过了2,3两个子任务
然后试图换成bitset，开了bitset<100005> b[100005]空间居然还没有爆炸。。。不过还是跑的很慢 只过了2,3两个点
然后发现直接用数组存就好了 每次新加入一堵墙和删除一堵墙时更新一下 这样就过了前4个子任务
发现对于颜色一样的墙，能染它们的染色公司也一样，所以只用处理每种颜色有哪些公司能染 然后加了一些玄学剪枝就AC了。。。???
跑的还挺快 最慢200ms
复杂度 (O()玄学())？
难点不在那个弱智dp 主要还是在如何快速判断能从哪些墙 (y) 开始染色
T2
T2第一眼看好像是和双连通分量之类的东西有关，然后照着样例试了下结论发现不太对。。。
然后感觉非常的不可做 看了下子任务，subtask1是链或环 subtask2是菊花图。。。好像挺简单？就是才13pts。。。
T3
所以就先去看T3了 作为一名只在CF做过交互题的选手，不太知道交互题该怎么入手。。。
不过前两个subtask还是比较简单的，直接暴力询问 (n^2) 次把整棵树的结构问出来
然后就从树的直径的一端开始，每次找到树上离当前点最远的点作为下一个游览点，然后把它删掉
然后subtask3是棵完全二叉树，树的结构已知，似乎可以口胡一下做法？
试了好几个算法都不对 最后写+调了1h调出来了一个挺奇怪挺复杂的找fun路径的一个算法 时间复杂度是 (O(nh)) 的，其中 (h) 是树高
显然完全二叉树的树高是 (log n) 所以我把这个点过了 加上前两个子任务就是47pts 开心
然后看subtask4 好像意思是说树有一个根并且点的编号就是dfs序？下面的另外两个条件看不太懂 所以就弃了这题
T2
然后回头把T2的前两个subtask写了 还被菊花图卡了半天。。。
写完发现自己就是个弱鸡 T2什么都想不出来
最后十分钟想到一个每次删一个点然后建最小生成树的玄学算法 一是不知道正确性 二是只剩10分钟了 所以就没去写了
最终得分100+13+47=160
wc，发晚了 度娘没给我送上搜索首页