| 比赛 | 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;
}