https://atcoder.jp/contests/agc032/tasks/agc032_b?lang=en
构造好题。
首先我们先造一个任两个点都有通路的图。
但是题目要求没有自环,所以删掉自环后,第 (i) 个点的权值为 (frac{N imes (N-1)}{2}-i)。
考虑怎样让每个点的权值相等。
给每个点再减去一个 (N-i) 即可,此时,第 (i) 个点的权值为 (frac{N imes (N-1)}{2}-i-(N-i)=frac{N imes (N-1)}{2}-N)。
这个时候,我们就要求 (N-i ot=i)。
显然,若 (i=frac{N}{2}) 且 (N) 为偶数时,(N-i=i)。
我们不可能删去同一条边两次,所以,考虑给删去 (N-i-1),这样第 (i) 个点的权值就为 (frac{N imes (N-1)}{2}-i-(N-i+1)=frac{N imes (N-1)}{2}-N-1)。
时间复杂度:(O(n^2))。