原题地址典型的二次递推/DP的题目。
首先，题目中的“不便利值”指的是某个点到根的路径上的木有被选定链覆盖的边的条数。
第一问：设F[i][0..2]分别为当子树i中结点i的状态为不参与链（0）、作为某链端点（1）、作为某链中间点（2）时，子树i中的结点到i的最小不便利值。为了得到F，需要设立G[j][k(0..2)]表示结点i的前j棵子树中，有k棵的根结点与结点i接上的最小的最大不便利值。显然，不和i接上的，状态为0、1、2都行，但不便利值要加1，而和i接上的状态只能是0或1，不加1。
问题是第二问。第二问的难点在于，
当i取得最小不便利值时，i的每个子结点并非都取到最小不便利值。举个例子，结点i的最小不便利值为3，它的某个子结点j的最小不便利值为2，则当j与i接上时，子树j的内部既可以取不便利值为2的解，也可以取不便利值为3的解。所以，为了解决第二问，需要求出结点i的最小不便利值为x的解的总数。
万幸的是，x的范围并不是太大，可以证明，x不会超过log3N（下取整），也就是当N=100000时x最大为10。因此，最后仍然不会T掉。
这题的一个启示就是，在求类似于“最优解计数”的问题中，
不要认为当后面的状态取得最优解时，前面的状态一定取得最优解。因此，不能只记录某状态取得最优解的个数，而要记录该状态取得每一个可行解时的个数。
代码：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 100010, MAXW = 11, INF = ~0U >> 2;
struct edge {
int a, b, pre, next;
} E0[MAXN * 3], E[MAXN << 1];
int n, m0, m, Q[MAXN], F[MAXN][3], G[MAXN][3], res1 = 0;
ll MOD, FS[MAXN][MAXW][3], S[MAXN][MAXW][3], res2 = 0;
bool vst[MAXN];
void init_d()
{
re(i, n) E0[i].pre = E0[i].next = E[i].pre = E[i].next = i; m0 = m = n;
}
void add_edge0(int a, int b)
{
E0[m0].a = a; E0[m0].b = b; E0[m0].pre = E0[a].pre; E0[m0].next = a; E0[a].pre = m0; E0[E0[m0].pre].next = m0++;
E0[m0].a = b; E0[m0].b = a; E0[m0].pre = E0[b].pre; E0[m0].next = b; E0[b].pre = m0; E0[E0[m0].pre].next = m0++;
}
void add_edge(int a, int b)
{
E[m].a = a; E[m].b = b; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m++;
}
void init()
{
int _M; scanf("%d%d", &n, &_M); cin >> MOD; if (_M < n - 1) {res1 = res2 = -1; return;} init_d(); int a0, b0;
re2(i, 1, n) {scanf("%d%d", &a0, &b0); add_edge0(--a0, --b0);}
}
void prepare()
{
re(i, n) vst[i] = 0; Q[0] = 0; vst[0] = 1; int x, y;
for (int front=0, rear=0; front<=rear; front++) {
x = Q[front];
for (int p=E0[x].next; p != x; p=E0[p].next) {
y = E0[p].b;
if (!vst[y]) {vst[y] = 1; Q[++rear] = y; add_edge(x, y);}
}
}
re(i, n) if (!vst[i]) {res1 = -1; res2 = -1; return;}
}
inline int minv3(int s1, int s2, int s3)
{
int s0 = s1 <= s2 ? s1 : s2;
return s0 <= s3 ? s0 : s3;
}
inline int minv2(int s1, int s2)
{
return s1 <= s2 ? s1 : s2;
}
void solve()
{
int x, y, len, v1, v2, v01, v02; ll sum;
rre(i, n) {
x = Q[i]; len = 0; G[0][0] = 0; G[0][1] = G[0][2] = INF;
for (int p=E[x].next; p != x; p=E[p].next) {
y = E[p].b; len++;
v1 = minv3(F[y][0], F[y][1], F[y][2]) + 1; v2 = minv2(F[y][0], F[y][1]);
G[len][0] = v1 >= G[len - 1][0] ? v1 : G[len - 1][0];
v01 = v1 >= G[len - 1][1] ? v1 : G[len - 1][1];
v02 = v2 >= G[len - 1][0] ? v2 : G[len - 1][0];
G[len][1] = minv2(v01, v02);
v01 = v1 >= G[len - 1][2] ? v1 : G[len - 1][2];
v02 = v2 >= G[len - 1][1] ? v2 : G[len - 1][1];
G[len][2] = minv2(v01, v02);
}
re(j, 3) F[x][j] = G[len][j];
re(j, MAXW) {S[0][j][0] = 1; S[0][j][1] = S[0][j][2] = 0;} len = 0;
for (int p=E[x].next; p != x; p=E[p].next) {
y = E[p].b; len++;
re(j, MAXW) re(k, 3) {
S[len][j][k] = 0;
if (j) {
sum = 0; re(k0, 3) {sum += FS[y][j - 1][k0]; if (sum >= MOD) sum -= MOD;}
S[len][j][k] = (sum * S[len - 1][j][k]) % MOD;
}
if (k) {
sum = 0; re(k0, 2) {sum += FS[y][j][k0]; if (sum >= MOD) sum -= MOD;}
S[len][j][k] = (S[len][j][k] + sum * S[len - 1][j][k - 1]) % MOD;
}
}
}
re(j, MAXW) re(k, 3) FS[x][j][k] = S[len][j][k];
}
res1 = minv3(F[0][0], F[0][1], F[0][2]);
res2 = 0; re(i, 3) if (F[0][i] == res1) res2 += FS[0][F[0][i]][i]; res2 %= MOD;
}
void pri()
{
cout << res1 << endl << res2 << endl;
}
int main()
{
init();
if (!res1) prepare();
if (!res1) solve();
pri();
return 0;
}