洛谷P4336 [SHOI2016]黑暗前的幻想乡 [Matrix-Tree定理，容斥]

传送门

思路

首先看到生成树计数，想到Matrix-Tree定理。

然而，这题显然是不能Matrix-Tree定理硬上的，因为还有每个公司只能建一条路的限制。这个限制比较恶心，尝试去除它。然而，这题