CF1060E Sergey and Subway

树上计数dp，考虑每条边的贡献，树上两点距离用深度与LCA表示

长度为2的两点间可以连一条边，所以对于任意两点$i,j$，$dis{2}_{i,j}=\lceil di{s}_{i,j}/2\rceil =(di{s}_{i,j}+(di{s}_{i,j}\%2==1))/2$
对于前半部分，我们要求原图上所有点对的距离，通过树形dp计算每条边对两端点集的贡献即可
对于后半部分，我们只需另外统计一下在原图中两点距离为奇数的点即可，对于任意两点：$di{s}_{i,j}=de{p}_i+de{p}_j-2\ast LC{A}_{i,j}$ 显然式子中的2*LCA不对奇偶产生影响，所以只需要处理出各点深度即可

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin>>n;vector<vector<int>> e(n+1);for (int i=1;i<n;i++){int a,b;cin>>a>>b;e[a].push_back(b);e[b].push_back(a);}vector<int> dep(n+1);vector<ll> sz(n+1);ll ans=0,cnt=0;function<void(int,int)> dfs=[&](int u,int fa){sz[u]=1;for (auto v:e[u]){if (v==fa) continue;dep[v]=dep[u]+1;dfs(v,u);sz[u]+=sz[v];}cnt+=(dep[u]%2==1);ans+=sz[u]*(n-sz[u]);};dep[1]=1;dfs(1,-1);cout<<(ans+cnt*(n-cnt))/2;return 0;
}