各种暴力搜索都行。
发现每次操作相当于是在染一个后缀。
于是考虑从左往右染,如果 ci=ci−1c_i=c_{i-1}ci=ci−1 说明 iii 不需要再染,否则就需要重新染。
注意到先染节点 111 一定最优,然后一次检查其他点与节点 111 颜色是否相同,不同就重新染。
根据链和菊花的解法受到启发,发现对于树的情况从上往下染即可,即 cu=cpuc_u=c_{p_u}cu=cpu 说明不需要再染,否则就重新染。
使用您的 Hydro 通用账户