#abc303e. [abc303_e]A Gift From the Stars

[abc303_e]A Gift From the Stars

一个具有 (k+1)(k+1) 个顶点和 kk 条边的图被称为一个级别为 kk2k(k\ge 2)的菊花图,当且仅当:

  • 它有一个顶点与其他 kk 个顶点之间通过一条边相连,而其他顶点之间没有边。

起初,我们有一个由多个菊花图组成的图。重复以下操作,直到整个图变为一张连通图:

  • 选择图中的两个顶点。其中顶点之间必须是不连通的,并且它们的度数必须都是 11。将这两个顶点用一条边连接起来。

然后,在该过程后,他将整数从 11NN 随机分配给图中的每个顶点。生成的图是一棵树,我们称其为 TTTT(N1)(N-1) 条边,第 ii 条边连接了 uiu_iviv_i

给定 T,从小到大输出一开始的每个菊花图的 kk