bzoj#P2314. 士兵的放置

士兵的放置

题目描述

八中有 nn 个房间和 n1n-1 双向通道,任意两个房间均可到达. 现在出了一件极 BT 的事,就是八中开始闹鬼了。老大决定加强安保,现在如果在某个房间中放一个士兵,则这个房间以及所有与这个房间相连的房间都会被控制. 现在老大想 知道至少要多少士兵可以控制所有房间. 以及有多少种不同的方案数.

输入格式

第一行一个数字 nn 代表有 nn 个房间,房间编号从 11 开始到 nn。下面将有 n1n-1 行,每行两个数,代表这两个房间相连。

输出格式

第一行输出至少有多少个士兵才可以控制所有房间第二行输出有多少种方案数,方案数会比较大,输出除以 10329929411032992941 的余数吧.

6
1 2
1 3
1 5
1 4
5 6
2
2

样例说明 1

第一种方案是将士兵放在 11 号房间及 66 号房间 第二种方案是将士兵放在 11 号房间及 55 号房间

数据规模与约定

对于 100%100\% 的数据,n<=500000n<=500000