阅读下面一段程序,完成(1)-(5)五道小题。



对于图G=(V,E)，我们定义它的线图L(G)为一张|E|个点的无向图,满足:

*原图G中的边e对应L(G)中的一个点u。

*L(G)中点u,v之间有连边，当且仅当G中u,v对应的边有公共的顶点。

下图展示了如何通过G构造出L(G)。



现在,给定一棵树T，你需要计算出它的k阶线图 L'(T) 的点数。

输入格式:输入的第一行包含两个整数n,k。接下来n-1行,每行两个整数u,v,描述树中的一条边。

输出格式:输出一行一个整数,表示答案。

数据范围:1≤k≤5,1≤n≤50。

#include<bits/stdc++.h>





const int N=5e3+7;


int n,k,d[N];


std::vector<int>p[N];


bool e[N][N];





int main() {


	scanf ("%d%d", &n,&k);


	--n;


	for (int i=1,x,y; i<=n; i++)


	{


		scanf ("%d%d",&x,&y);


		for (int j:p[x]) e[i][j]=e[j][i]=1;


		for (int j:p[y]) e[i][j]=e[j][i]=1;


		___(1)__;


	}


	int ans=0;


	if (k==2)


	{


		for (int i=1; i<=n; i++)


			for (int j=1; j<=n; j++)


				___(2)__;


		___(3)__;


	}


	else if (k==3)


	{


		for (int i=1; i<=n; i++)


			for (int j=1; j<=n; j++)


				d[i]+=e[i][j];


		for (int i=1; i<=n; i++)	___(4)__;


	}


	else if (k==4)


	{


		for (int i=1; i<=n; i++)


			for (int j=1; j<=n; j++) d[i]+=e[i][j];


		for (int i=1; i<=n; i++)


			for (int j=1; j<=n; j++)


				if (e[i][j])


					___(5)__;


		ans /=4;


	}


	else if (k==5)


	{


		for (int i=1; 1<=n; i++)


			for (int j=1; j<=n; j++) d[i]+=e[i][j];


		static int c[N][N];


		for (int i=1; 1<=n; i++) {





			int x1=0,x2=0;


			for (int j=1; j<=n; j++)


				if(e[i][j])


					c[i][j]=d[i]+d[j]-3, x1+=c[i][j],x2+=c[i][j]*c[i][j];


			for (int j=1; j<=n; j++)


				if (e[i][j])


					ans+=(d[i]-1)+c[i][j]+e[i][j], ans+-2*c[i][j]*(x1-c[i][j]),ans+=x2-c[i][j]*e[i][j], ans-=(d[i]-1)*c[i][j], ans-=x1-c[i][j];


		}


		ans /=4;


	}


	printf ("%d",ans);


	return 0;


}

选择题