原題地址典型的二次遞推/DP的題目。
首先，題目中的“不便利值”指的是某個點到根的路徑上的木有被選定鏈覆蓋的邊的條數(shù)。
第一問：設(shè)F[i][0..2]分別為當子樹i中結(jié)點i的狀態(tài)為不參與鏈（0）、作為某鏈端點（1）、作為某鏈中間點（2）時，子樹i中的結(jié)點到i的最小不便利值。為了得到F，需要設(shè)立G[j][k(0..2)]表示結(jié)點i的前j棵子樹中，有k棵的根結(jié)點與結(jié)點i接上的最小的最大不便利值。顯然，不和i接上的，狀態(tài)為0、1、2都行，但不便利值要加1，而和i接上的狀態(tài)只能是0或1，不加1。
問題是第二問。第二問的難點在于，
當i取得最小不便利值時，i的每個子結(jié)點并非都取到最小不便利值。舉個例子，結(jié)點i的最小不便利值為3，它的某個子結(jié)點j的最小不便利值為2，則當j與i接上時，子樹j的內(nèi)部既可以取不便利值為2的解，也可以取不便利值為3的解。所以，為了解決第二問，需要求出結(jié)點i的最小不便利值為x的解的總數(shù)。
萬幸的是，x的范圍并不是太大，可以證明，x不會超過log3N（下取整），也就是當N=100000時x最大為10。因此，最后仍然不會T掉。
這題的一個啟示就是，在求類似于“最優(yōu)解計數(shù)”的問題中，
不要認為當后面的狀態(tài)取得最優(yōu)解時，前面的狀態(tài)一定取得最優(yōu)解。因此，不能只記錄某狀態(tài)取得最優(yōu)解的個數(shù)，而要記錄該狀態(tài)取得每一個可行解時的個數(shù)。
代碼：
#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;
}