P4059
AT_ABC180_e
看见数据范围想状压，再看见最短路径增加一维。但是我们要注意，这个题中之所以可以直接做是因为重复走的路径与直接走的路径一定形成了三角不等式的关系，所以每个点会且只会走一次。
P1220
经典的区间dp, 我们发现只会在区间端点决策，所以状态设为 \(f_{l,r,0/1}\) 表示区间 \([l,r]\) 里全部的灯是关上的，0/1表示在区间左侧端点和右侧端点。这样直接 \(O(n^2)\) 转移，每次考虑是跨过整个区间关另一边的灯， 还是关同侧的灯。
答案就是 \(min(f_{1,n,0},f_{1,n,1})\)
CF1882D
根据异或的性质（两个不同的数异或同一个数后仍不同），所以我们就考虑设 \(f_u\) 表示把以 \(u\) 为根的子树全部修改为根节点的权值所花费的最小代价。
接下来考虑不同的根的答案。好做每次考虑往当前根 \(u\) 的某个儿子 \(v\) 走一步，发现所有需要的 (\(f_u\) , \(f_v\) , \(size_u\) , \(size_v\)) 全部都有，直接计算即可