记录编号	58175	评测结果	AAAAAAAAAA
题目名称	计划	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.953 s
提交时间	2013-04-17 20:52:30	内存使用	5.11 MiB

#include<fstream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstdio>
using namespace std;
ifstream fi("plan.in");
ofstream fo("plan.out");
bool pic[1001][1001];//矩阵存图
vector <int> point[1001];//链表存图
bool boo[1001]={false},dry[1001]={false},ch[1001]={false},used[1001]={false};
int n,m,k;
string f[1001][1001];
bool check(string x,string y)//x>=y?
{
	if((x.length()>y.length())||(x.length()==y.length()&&x>=y))return true;
	return false;
}
void dfs(int x)
{
	ch[x]=true;//用了x节点
	used[x]=true;
	for(int y=1;y<=n;y++)
		if((!ch[y])&&(x!=y)&&pic[x][y])//y没用过且图里有这条边
		{
			point[x].push_back(y);
			dfs(y);
		}
	ch[x]=false;
}
string mul(string a,string b)//高精度乘法
{
	string c;
	int la,lb,lmax,i,j,sa[1001]={0},sb[1001]={0},cc[1005]={0};
	la=a.length();lb=b.length();
	for(i=la-1;i>=0;i--) sa[la-i]=a[i]-48;
	for(i=lb-1;i>=0;i--) sb[lb-i]=b[i]-48;
	for(i=1;i<=la;i++)
	{
		for(j=1;j<=lb;j++)
		{
			cc[i+j-1]+=sa[i]*sb[j];
			cc[i+j]+=cc[i+j-1]/10;
			cc[i+j-1]=cc[i+j-1]%10;
		}
		j=i+lb-1;
		while(cc[j]>=10)
		{
			cc[j+1]+=cc[j]/10;
			cc[j]=cc[j]%10;
			j++;
		}
	}
	lmax=1004;
	while(cc[lmax]==0&lmax>1){lmax--;}
	c="";
	for(i=lmax;i>=1;i--) c+=char(cc[i]+48);
	return c;
}
string makeit(int x)
{
	int z=x;
	char y;
	string c="";
	while(z/10>0)
	{
		y=(z%10)+48;
		c+=y;
		z=z/10;		
	}
	y=z+48;
	c+=y;
	return c;
}
int main()
{
	fi>>n>>m>>k;
	int i,j,p,q;
	for(i=0;i<=1000;i++)
		for(j=0;j<=1000;j++)
			pic[i][j]=false;
	string modd;
	for(i=1;i<=k;i++)fi>>j,dry[j]=true;
	for(i=1;i<=n-1;i++)
	{
		fi>>p>>q;
		pic[p][q]=true;
		pic[q][p]=true;
	}
	dfs(1);
	for(i=1;i<=n;i++)
		if(point[i].size()==0)boo[i]=true;
			else boo[i]=false;
	//====================================
	for(i=0;i<=1000;i++)
		for(j=0;j<=1000;j++)
			f[i][j]="-";
	f[0][1]="1";//消耗0天物资能到1,几率为1/1.f记录分母
	int first=n+1,last=0;
	string fir="0",las="1";
	//====================================
	for(i=0;i<m;i++)
	{
		for(j=1;j<=n;j++)
		if(f[i][j]!="-")
		{
			q=point[j].size();
			modd=makeit(q);//改为string来乘
			for(p=0;p<q;p++)
				if(dry[j])
					f[i+2][point[j][p]]=mul(f[i][j],modd);
				else
					f[i+1][point[j][p]]=mul(f[i][j],modd);
				//================================================
				if(boo[j])//j可开发
				{
					//fo<<j<<' '<<f[i][j]<<endl;
					if(first==n+1||check(fir,f[i][j]))
					{
						if(f[i][j]==fir&&first<j)goto BYE1;
						first=j;
						fir=f[i][j];
						BYE1:;
					}
					if(last==0||check(f[i][j],las))
					{
						if(f[i][j]==las&&last<j)goto BYE2;
						last=j;
						las=f[i][j];
						BYE2:;
					}
				}
		}
	}
	for(j=1;j<=n;j++)
	{
		if(!used[j])//有些点没跟其他任何点连着,到达可能性为0
		{
			if(last<j)goto BYE3;
			last=j;
			BYE3:;
		}
	}
	/*
	for(j=1;j<=n;j++)
	{
		fo<<j<<' ';
		for(i=0;i<=m;i++)
			fo<<f[i][j]<<"   ";
		fo<<endl<<endl;
	}*/
	//fo<<used[111]<<endl;
	fo<<last<<endl<<first<<endl;
	fi.close();
	fo.close();
	return 0;
}