CF1919H Tree Diameter

发布时间 2024-01-08 21:32:39作者: zhouhuanyi

某人在换根时根还设置成 \(1\) 交了整整 \(11\) 发,我不说是谁。

先考虑一下 \(2\) 询问的实际用途,因为我们可以用它来确定深度,根据树上交互题的常见技巧,我们通过这种方式确定了一个拓扑序,只要能在拓扑序的前缀中快速查询一个点的父亲,就可以求出这棵树。

考虑先以一条边为根,那么其会有至多两个子树,先考虑一个弱化 \(\text{case}\) 即只有一个子树的情况怎么做。不难发现 \(1\) 询问实际是强的,如果要查一个深度为 \(i\) 的边,将根和自己设置为 \(2\times 10^6\),所有深度为 \(i-1\) 的边设置为 \(num\times 10^3\),其他的仍设置为 \(1\)。这样一定会取自己到根的连线,而众多的 \(1\) 也不会超过 \(10^3\),最后查询时减去 \(2\times 10^6\) 再除 \(10^3\) 下取整即可。

但如果有两颗子树实际是困难的,因为我们上述的操作实际上是将树的直径的一个端点避到根出了,而树的直径必然在叶子处,所以如果所有叶子的深度均相等。那么我们在加入深度为 \(i\) 的边时,无论如何都会有两个点是直径端点,那么直径端点的两个子树之间就无法进行区分,但只要有一个深度不相等的叶子,就可以把它作为根,这样就可以按照上述做法做了。

现在我们考虑所有叶子节点深度均相等的情况,这样由于每个深度小于叶子的节点都有至少一个子节点,所以对于每个深度为该深度的点的个数序列 \(\text{cnt}\) 一定是不降的,而且一旦出现了所有叶子节点深度存在不相等的情况,那么花费最多 \(2\) 的额外代价是允许的,因为这种情况至多出现一次。

直接将每个深度为 \(i-1\) 的边设置为 \(num\times 10^3\) 的问题在上文已经描述过了,因为两个直径端点不能作为区分,同上的即为最大值与次大值区分不开,这样就要使用额外代价,是不能作为总的考虑的。

但是如果我们可以得到两个点的父亲信息并,每次选择其中一个深度为 \(i\) 的边 \(x\) 和其他所有 \(i\) 的边做信息求并,那么如果出现了三种本质不同的信息,则出现的众数则为 \(x\) 的父亲边。通过信息并也容易快速还原其他边的父亲信息,但退化情况即为只出现 \(\leqslant 2\) 种的情况,是可以额外考虑的。

先考虑为 \(1\) 的情况,由于 \(\text{cnt}\) 数组不降,\(cnt_{i-1}\geqslant cnt_{1}\geqslant 2\),则其之后必然会破坏所有叶子节点深度均相等的性质,是可以付出额外代价的,此时如果 \(cnt_{i-1}>2\),在使用前面所说的不能区分直径端点的询问方式的前提下将值域取反再问一次必然有至少一次可以确定。但当 \(cnt_{i-1}=2\) 时其实用 \(1\) 询问无法确定,因为两个深度为 \(i-1\) 的点分别是直径端点,但此时这个图是对称的,所以这个点的父亲设置为任何一个都可以。

再考虑 \(2\) 的情况,实际上和 \(1\) 差不多,对于 \(cnt_{i-1}>2\) 一定也会破坏,可以按上述方法做,对于 \(cnt_{i-1}=2\) 的情况由于对称性任意设置都可以,但要满足父亲不同的一定还是父亲不同,即两种方式任选一种都可以。

现在关键的问题在于如何得到两个点的父亲信息并,注意到维护信息并是困难的,但求信息和是容易的,直接将两个位置设置为 \(2\times 10^6\),再将所有深度为 \(i-1\) 的边设置为 \(num\times 10^3\) 即可。直接构造两两求和各不相同的序列经过实验表明构造 \(1000\) 个数值域需要达到 \(13951623\),再乘上 \(1000\) 是爆 \(10^9\) 的。虽然其意味着更少的询问次数,但注意到上述过程实际上少消耗了一次 \(1\),其实可以只求和,那么此时如果存在 \(a,b\)\(a,c\)\(pair\)\(a+b\not=a+c\),所以我们只要任意找两个和不同的边 \(y,z\),再问一下 \(y,z\) 可以知道 \(b+c\),可以解出 \(a\),那么就可以还原所有父亲(特别要注意的是对于父亲相同的情况上述询问方式会得到 \(0\),此时相当于求出了一个与其相等的等价类,需要特殊处理)。

综上即可做到 \(n-1\)\(1\) 询问,\(n-2\)\(2\) 询问。