由题意可知，在原图中经过边数为 \(2\) 的一对点，在新图中经过边数为 \(1\)。所以每对点在新图中的距离为：
\[\begin{aligned}
\lceil \frac{dis(i,j)}{2} \rceil = \frac{dis(i,j)+dis(i,j)\;mod\;2}{2}
\end{aligned}
\]
那么我们只需在原图上求出任意两点距离之和并加上 \(dis\) 为奇数的个数，最后除以 \(2\) 即可。
如果暴力枚举，必然超时。我们转换思路，求每条边的贡献——这条边 \(\texttt {左边的点的个数} \times 右边的点的个数\)。
现在思考，怎么统计两点距离为奇数的个数：
对于点 \(x,y\)，\(dis(x,y)=dep(x)+dep(y)-2\times dep(LCA(x,y))\)。\(LCA\) 的 \(dep\) 不会影响距离的奇偶性，所以可以只考虑 \(x\) 和 \(y\) 深度的奇偶性。假设此时有 \(cnt_0\) 个深度为偶数的点，有 \(cnt_1\) 个深度为奇数的点，则它们两两配对，能构成的 \(dis\) 为奇数的个数为 \(cnt_0\times cnt_1\)。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll ans,sz[200100],dep[200100],cnt[2];
int n;
vector<int> G[200100];
void dfs(int now,int fa){
sz[now]=1;dep[now]=dep[fa]+1;
cnt[(dep[now]&1)]++;
for(int i=0;i<G[now].size();i++){
int to=G[now][i];
if(to==fa) continue;
dfs(to,now);
sz[now]+=sz[to];
ans+=(n-sz[to])*sz[to];
}
}
int main(){
cin>>n;
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,1);
cout<<(ans+cnt[0]*cnt[1])/2<<endl;
return 0;
}