#381. 【UTR #1】ydc的大树

【UTR #1】ydc的大树

当前没有测试数据。

以1号点为根节点

一个黑点如果有多个相邻的节点出去都能找到最远的黑点,那么这个黑点就是无敌的

所以考虑每个黑点x的最远距离和最远点是否仅在一个“方向”

然后这个方向的一些连续白点割掉可以使得x不高兴

1.如果都在一个方向,假设是x的子树,那就是这个子树最远黑点们的lca到x路径上的任意白点割掉,都可以使得x不高兴

2.如果都在往父亲的方向,找到最浅的点p,使得每个最远黑点到x的路径都经过p,p到x的路径上的任意白点割掉,都可以使得x不高兴

树形DP即可。

struct,记录最远距离、最远的方向个数、决策位置(1的lca或者是2的p)

转移较麻烦

树上差分打标记即可。

求lca,所以O(nlogn)