[ARC108F] Paint Tree

前言

复习什么的就留到下周了, 顺便把格式调好

现在把每日一练打了差不多

今天补了一下午的 \(\rm{T2}\) , 终于还是被码力问题击碎了, 不过也还好

这道题是模拟赛 \(\rm{T3}\)

吉司机线段树和左偏树都只能明天搞了, 明天把 \(\rm{C}\) 打了开摆

思路

首先那几个 \(\rm{subtask}\) 都没有 \(\rm{T2}\) 难, 就不管了

然后就是正解思路

首先, 这种题一般要根据答案算方案数
所以我们考虑计算答案等于 \(d\) 的方案数, 至少要求出对于任意一个点, 离他的距离 \(> d\) 的点的位置

解决方法如下

先求出一条直径, 若直径的两个端点颜色相同, 则最长距离一定为直径
否则, 令两个端点分别为 \(x,y\) , 并钦定 \(x, y\) 不同色
枚举答案 \(d\) , 所有到 \(x\) 距离 \(>d\) 的点颜色必须与 $ y$ 一样, 所有到 $ y$ 距离 $ > d$ 的点颜色必须和 $ x$ 一样

考虑证明为什么要取直径的两个端点
由于 $ x, y$ 是直径的两个端点, 可以发现, 若一个点 $ z$ 到 $ x, y$ 的距离都不超过 $ d$ , 则其到任何一个点的距离不超过 $ d$ , 所以 $ z$ 的颜色并不会对答案产生影响

所以, 定义 $ cnt_i$ 表示到直径两端的距离不超过 $ i$ 的点数 , 定义 $ f_d$ 表示答案不超过 $ d$ 的树的形态数, $ g_d$ 表示答案为 $ d$ 的树的形态数, $ dis_{1/2}$ 表示从直径的两端点出发到其他点的距离
定义 $ L=\max (\min(dis1_i,dis2_i))$ 的意义为, 在所有形态的树中, 最小的答案(同色点对最大距离) , 对于每个点取到直径两端点近的那个颜色即可

最终的总权值为 $ \displaystyle\sum\limits_{i=L}^S g_i\times i$

容易得到 $ f_d=2^{cnt_d}$
。但是我们想要答案等于 $ d$
的树的形态数 $ g_i$
。很明显, 只需要容斥减去 $ f_{d-1}$
即可, 也就是 $ g_d=f_d-f_{d-1}$
。

注意 $ x,y$
共有 $ 2$
种颜色分配方案。

我的理解是, 你要知道对于每个点, 到他的距离 \(> d\) 的点有哪些, 从而通过确定这个点的颜色来确定到他的距离 \(> d\) 的点的颜色, 像是一个连通块的样子
然后你发现一个点是没有用的, 仅当其到任何点的距离都 \(\leq d\) , 联想到直径

你发现确定一个点, 可以递归确定所有到某个点距离 \(> d\) 的点的颜色, 考虑怎么确定
你发现直径 \((x, y)\) 的一个性质
如果 \(dis(u, v) > d\) , 那么一定有 \(dis(u, x) > d\) 或者 \(dis(u, y) > d\) , \(dis(v, x) > d\) 或者 \(dis(v, y) > d\) , 其中 \(u, v\) 异色, 你发现对于两个有用的点, 如果不是异色一定是同色的

具体证明一下, 如果存在 \(dis(u, x) > d\) 且 \(dis(v, x) > d\) , 一定不存在染色, 所以不管这种情况, 还有 \(dis(u, y) > d\) 且 \(dis(v, y) > d\)
分成两种情况讨论

• \(dis(u, x) > d, dis(v, y) > d\)
• \(dis(u, y) > d, dis(v, x) > d\)

发现两种情况本质相同, 只是 \((u, v)\) 的顺序问题
我们只考虑 \(dis(u, x) > d, dis(v, y) > d\) , 也一定能考虑到所有点对 \((u, v)\)

分类讨论之后, 你确定 \(x\) 的颜色, 就可以确定所有 \(u\) 的颜色, 确定 \(y\) 的颜色, 就可以确定所有 \(v\) 的颜色, 还是很好做的

总结

树上距离最大的问题, 往往可以向直径的方向转化

巧妙地地方在, 利用了直径的好性质

这种异色约束, 考虑找性质「异异得正」