P4084 [USACO17DEC] Barn Painting G

Farmer John 有一个大农场，农场上有 $N$ 个谷仓（$1 \le N \le 10^5$），其中一些已经涂色，另一些尚未涂色。Farmer John 想要为这些剩余的谷仓涂色，使得所有谷仓都被涂色，但他只有三种可用的油漆颜色。此外，他的获奖奶牛 Bessie 如果发现两个直接相连的谷仓颜色相同，会感到困惑，因此他希望确保这种情况不会发生。 保证 $N$ 个谷仓之间的连接不会形成任何“环”。也就是说，任意两个谷仓之间最多只有一条连接路径。 Farmer John 有多少种方式可以为剩余的未涂色谷仓涂色？

无

无