526互联

[AGC005C] Tree Restoring 题解

发布时间 2023-08-21 16:26:46作者: Al_lA

比较简单的题。

思路

我们可以把一棵树抽象成一条极长的链上挂了很多的点。

观察这样的树的性质。

除去中间的每一个 \(dis\) 至少有两个点的 \(a_i=dis\)。

考虑这条链的长度为 \(s\)。

那么对于中间的点，我们可以分两种情况讨论。

  1. \(s\) 为偶数

    那么我们必然要求在中间的权值只有一个。

    否则无法构成一棵树。

  2. \(s\) 为奇数

    与偶数类似。

    那么我们必然要求在中间的权值有且仅有两个。

那么我们只需要把这几种情况判断一下即可。

Code

AC记录。