比赛 不平凡的世界 评测结果 MMMMMMMMMM
题目名称 不平凡的许愿树 最终得分 0
用户昵称 321Rain 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2015-11-05 11:11:34
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<cmath>
#include<stack>
#include<cstdlib>
using namespace std;
struct N{
	int x,step;
};
int n;
vector<int> p[5100];
int vis1[5100][5100];
int vis2[5100][5100];
int vis3[5100][5100];
int ans;
int a1,a2,a3;
bool vis[5100];
int dis[5100][5100];
void bfs(int x,int y)
{
	if (dis[x][y]>0)
	{a1=dis[x][y];return;}
    queue<N>q;
    N a;
    memset(vis,0,sizeof(vis));
    q.push((N){x,0});
    while (!q.empty())
    {
    	a=q.front();
    	q.pop();
    	for (int i=0;i<p[a.x].size();i++)
        {
        	int ki=p[a.x][i];
        	if (vis[ki]) continue;
        	if (ki==y)
        	{
        		a1=a.step+1;
        	    dis[x][y]=a1;
				return;
			}
			q.push((N){ki,a.step+1}),vis[ki]=true;
		}
	}
}
int main()
{
	freopen("hopetree.in","r",stdin);
	freopen("hopetree.out","w",stdout);
	cin>>n;
	for (int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		p[x].push_back(y);
		p[y].push_back(x);
	}
	for (int i=1;i<=n;i++)
	 for (int j=1;j<=n;j++)
	 {
	 	if (i!=j)
	 	for (int k=1;k<=n;k++)
	 	if (k!=i&&k!=j)
	 	{
	 			bfs(i,j);
	 			int p1=a1;
	 		//	cout<<i<<"--->"<<j<<": "<<a1<<endl;
	 			bfs(j,k);
	 			int p2=a1;
	 		//	cout<<j<<"--->"<<k<<": "<<a1<<endl;
	 			bfs(k,i);
	 			int p3=a1;
	 		//	cout<<k<<"--->"<<i<<": "<<a1<<endl;
	 			if (p1==p2&&p2==p3)
	 			{
	 		//		cout<<i<<"---"<<j<<"---"<<k<<"***"<<endl;
	 			 	ans++;
	 		    }
		}
	 }
	ans/=6;
//	cout<<ans<<endl;
	cout<<ans%338+1<<" "<<(ans+233)%338+1;
	return 0;
	fclose(stdin);
	fclose(stdout);
}