记录编号 572765 评测结果 AAAAAAAAAA
题目名称 [CF1060E]Sergey and Subway 最终得分 100
用户昵称 Gravatar遥时_彼方 是否通过 通过
代码语言 C++ 运行时间 0.250 s
提交时间 2022-07-10 13:36:53 内存使用 89.46 MiB
显示代码纯文本
#include<bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define drep(x,y,z) for(int x=y;x>=z;x--)
#define ull unsigned long long
#define ll long long
using namespace std;
inline int read()
{
	int x=0;bool flag=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')flag=0;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	if(flag) return x;
	return ~(x-1);
} 
inline void write(int x)
{
	if(x<0) {x=~(x-1);putchar('-');}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
/////////////////////////
const int N=2e5+50;
int ioo[31000000];
ll nc;
struct G
{
	int ar;
	int nx;
}a[N<<1];
int aj;
int hd[N];
inline void ADD(int x,int y)
{
	a[++aj].ar=y;
	a[aj].nx=hd[x];
	hd[x]=aj;
}
ll ans;
ll b[2];
ll dfs(int cl,int fa,int dep)
{
    b[dep]++;
    dep^=1;
    ll sum=1;
    for(int i=hd[cl];i;i=a[i].nx)
    {
        if(a[i].ar==fa) continue;
        sum+=dfs(a[i].ar,cl,dep);
    }
    ans+=sum*(nc-sum);
    return sum;
}
int main()
{
    freopen("Sergeyas.in","r",stdin);
	freopen("Sergeyas.out","w",stdout);
    nc=read();
    int s1,s2;
    rep(i,2,nc)
    {
    	s1=read(),s2=read();
		ADD(s1,s2);
		ADD(s2,s1); 
	}
	dfs(1,1,0);
	ans>>=1;
	ans+=((b[1]*b[0])>>1)+((b[1]*b[0])&1);
	cout<<ans<<endl;
    return 0;
}