比赛 EYOI暨SBOI暑假快乐赛5th 评测结果 AAATTTTTTT
题目名称 Sergey and Subway 最终得分 30
用户昵称 ZRQ 运行时间 7.133 s
代码语言 C++ 内存使用 8.79 MiB
提交时间 2022-06-29 10:57:39
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int N=200005;
int n,hd[N],nxt[N],e[N],idx,d[N];
ll ans;
void add(int u,int v)
{
	nxt[++idx]=hd[u],hd[u]=idx,e[idx]=v;
}
void DFS(int nw,int fa)
{
	for(int i=hd[nw];i;i=nxt[i])
		if(!d[e[i]]&&e[i]!=fa)
			d[e[i]]=d[nw]+1,DFS(e[i],nw);
	return ;
}
int main()
{
	freopen("Sergeyas.in","r",stdin);
	freopen("Sergeyas.out","w",stdout);
	scanf("%d",&n);
	int x,y;
	for(int i=1;i<n;++i)
	{
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<n;++i)
	{
		DFS(i,0);
		for(int j=i+1;j<=n;++j)
			ans+=(d[j]>>1)+(d[j]&1);
		memset(d,0,sizeof(d));
	}
	printf("%lld\n",ans);
	return 0;
}