数学赛高！/数学さいこう！
嘛，这题有两种做法：
1、BYVoid的，不能说差，但至少是在考场上能最快冒出来的想法，之后需要优化，而且这个优化在考场上难以想出。
2、某50行代码，效率很好，但是得有一定的数学功底。
先说说BYVoid大神的算法，有\(F_{i,b}\)和\(G_{i,b}\)两个数组。
这里，\(F_{i,b}\)是指，节点\(i\)下面有若干个子节点，\(i\)向下连2条铁路（即\(i\)在线路中间），且不便利度不超过\(b\)，显然，其前提条件是，\(i\)得父节点没有向\(i\)建铁路
\(G_{i,b}\)是指，节点\(i\)下面有若干个子节点，\(i\)向下连1条或0条铁路（即\(i\)在线路两段，或不在线路上），且不便利度不超过\(b\)。
所以，我们有：
\[F_{i,b}=\sum_{j,k,l\in i\rightarrow SONs}(G_{j,b}G_{k,b}\Pi(F_{l,b-1}+G_{l,b-1}))\]和：
\[G_{i,b}=\sum_{j,l\in i\rightarrow SONs}(G_{j,b}\times \Pi(F_{l,b-1}+G_{l,b-1})) + \Pi(F_{l,b-1}+G_{l,b-1})\]特别的，当\(b=0\)时，我们有：
\[F_{i,0}=\begin{cases}G_{j,b}\cdot G_{k,b},i\ has\ 2\ child\ nodes\\0,Other\ cases\end{cases}\] \[G_{i,0}=\begin{cases}1,i\ has\ NO\ child\ node\\G_{i\rightarrow son,0},i\ has\ 1\ child\ node\\0,Other\ cases\end{cases}\]这是BYVoid的50分做法，非常好想，但是上面的优化很难，-〉BYVoid的完整题解
再说说一个非常好的做法
我们知道，对于一条边\(i\rightarrow v\)，我们有两种方法，要么建铁路，要么不建（笑……）
记\(R_0\)表示这条边不建铁路，它的儿子们能有的情况数
记\(R_1\)表示这条边建上铁路，它的儿子们能有的情况数
记\(F_{i,a,b}\)表示节点\(i\)向下牵\(a\)条边，最大不便利度为2的方案数
有\(R_0=F_{v,0,b-1}+F_{v,1,b-1}+F_{v,2,b-1}\)
和\(R_1=F_{v,0,b}+F_{v,1,b}\)
那么，就有
\[F_{i,2,b}=F_{i,2,b}\times R_0+F_{i,1,b}\times R_1\] \[F_{i,1,b}=F_{i,1,b}\times R_0+F_{i,0,b}\times R_1\] \[F_{i,0,b}=F_{i,0,b}\times R_0\]至此AC
下面是一些细节：
\(MOD\times 9997\)的目的是区别真0（本来就没有结果）和假0（取模后恰为0）
由于\(MOD\)可取很大的数，所以要开long long
由于状态不会重复，所以记搜没意义了（笑……）
下面是这种做法的AC-Code
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN=100005,MAXM=100005;
struct Edge{int t,next;}E[MAXM*2];
int pStart[MAXN];
int M,N;
long long MOD;bool MOD_FLAG=false;
long long F[MAXN][3][10];//F[i][a][b]=从节点i向下引出a条节点，不便利值为b的方案数
int RES;
void addedge(int u,int v,int m)
{
E[m].t=v;E[m].next=pStart[u];pStart[u]=m;
}
int dp(int i,int fa)//节点i，节点i他爸
{
int v,p;
F[i][0][RES]=1;
long long R0,R1,R2;
for (int p=pStart[i];p;p=E[p].next)
{
v=E[p].t;
if (v==fa)
continue;
dp(v,i);
R0=(F[v][0][RES-1]+F[v][1][RES-1]+F[v][2][RES-1])%MOD;
R1=(F[v][0][RES]+F[v][1][RES])%MOD;
F[i][2][RES]=(F[i][2][RES]*R0+F[i][1][RES]*R1)%MOD;
F[i][1][RES]=(F[i][1][RES]*R0+F[i][0][RES]*R1)%MOD;
F[i][0][RES]=(F[i][0][RES]*R0)%MOD;
}
return F[i][2][RES]+F[i][1][RES]+F[i][0][RES];
}
bool init()
{
int tu,tv;
scanf("%d%d%lld",&N,&M,&MOD);
if (MOD<10000)
{
MOD*=9997;
MOD_FLAG=true;
}
if (M!=N-1)
return false;
for (int i=1;i<=M;i++)
{
scanf("%d%d",&tu,&tv);
addedge(tu,tv,i);
addedge(tv,tu,i+M);
}
return true;
}
int main()
{
if (init())
{
for (RES=0;RES<=10;RES++)
if (dp(1,0))
break;
if (MOD_FLAG)
MOD/=9997;
printf("%d\n%lld\n",RES,(F[1][2][RES]+F[1][1][RES]+F[1][0][RES])%MOD);
}else
{
printf("-1\n-1\n");
}
return 0;
}