AtCoder Regular Contest 108

A Sum and Product

\(O(\sqrt{n})\) 枚举约数判断即可。

B Abbreviate Fox

用栈维护，每次判断栈顶是不是 fox，是则弹出。

C Keep Graph Connected

猜想一定有解。

猜想任何一个生成树都有解。

考虑构造生成树上的解。

以 \(1\) 为根，将每个节点的颜色都设成其与父亲连边的颜色，根节点设成所有连边中未出现的颜色。

这样可能不满足“恰好一个端点颜色相同”的限制，实际上这个问题的处理是独立的，把每条有这样情况的深度递增的链独立出来，只需要按照 \(101010\) 的顺序在保留颜色或改为所有连边中未出现的颜色，就可以保证链上边的有端点颜色相同且相邻节点颜色不同。