记录编号	415055	评测结果	AAAAAAAAAA
题目名称	[NOI 2008]设计路线	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.833 s
提交时间	2017-06-15 16:10:45	内存使用	51.89 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m,p,w[N*2],head[N],next[N*2];
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int mul(int x,int y){return (ll)x*y%p;}
void add(int f,int t){
	static int cnt=0;
	w[++cnt]=t;
	next[cnt]=head[f];
	head[f]=cnt;
}
int h[N][4],H[4],ans;
void work(int x,int fa){
	h[x][0]=h[x][1]=h[x][2]=0;
	for (int i=head[x];i;i=next[i]){
		int v=w[i];
		if (v==fa) continue;
		work(v,x);
		for (int i=0;i<3;i++) H[i]=1e9;
		for (int i=0;i<3;i++){
			H[i]=min(H[i],max(h[x][i],h[v][2]+1));
			H[i+1]=min(H[i+1],max(h[x][i],h[v][1]));
		}
		for (int i=0;i<3;i++) h[x][i]=H[i];
	}
	for (int i=1;i<3;i++) h[x][i]=min(h[x][i],h[x][i-1]);
}
//由树剖算法可以证明,第一问答案大于logn 
//dp[i][k][j]表示以i为根的子树,到根轻链数最大为j的方案数 
//且与i相连的边已经取了k条 
//f[x]表示能dp[x][0]+dp[x][1],g[x]表示dp[x][2] 
int dp[N][4][21],DP[4][21],f[N][21],g[N][21];
bool vis[N];
void solve(int x){
	vis[x]=1;
	dp[x][0][0]=1;
	for (int i=head[x];i;i=next[i]){
		int v=w[i];
		if (vis[v]) continue;
		solve(v);
		for (int k=0;k<3;k++)
		for (int i=0;i<=ans;i++)
			DP[k][i]=0;
		for (int k=0;k<3;k++)
		for (int i=0;i<=ans;i++)
		for (int j=0;j<=ans;j++){
			//不取这条边 
			int now=max(i,j+1);
			DP[k][now]=inc(DP[k][now],mul(dp[x][k][i],inc(f[v][j],g[v][j])));
			//取这条边 
			now=max(i,j);
			DP[k+1][now]=inc(DP[k+1][now],mul(dp[x][k][i],f[v][j]));
		}
		for (int k=0;k<3;k++)
		for (int i=0;i<=ans;i++)
			dp[x][k][i]=DP[k][i];
	}
	for (int i=0;i<=ans;i++){
		f[x][i]=inc(dp[x][0][i],dp[x][1][i]);
		g[x][i]=dp[x][2][i];
	}
}
int main()
{
	freopen("design.in","r",stdin);
	freopen("design.out","w",stdout);
	scanf("%d%d%d",&n,&m,&p);
	if (m<n-1) return puts("-1\n-1"),0;
	for (int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	work(1,0);
	ans=h[1][2];
	solve(1);
	printf("%d\n",ans);
	printf("%d\n",inc(f[1][ans],g[1][ans]));
	return 0;
}