CF1060E Sergey and Subway 题解

Libra_ / 2023-08-16 / 原文

题面

由题意可知，在原图中经过边数为 \(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;
}