【CodeForces】【思维】【DP】1060E-Sergey and Subway

CodeForces 1060E Sergey and Subway

◇题目传送门◆

前言

感谢Tiw_Air_OAO dalao对我的提示，使我从迷茫走向AC。

题目大意

给定一张有$N$个节点的树形图$G$，若图上存在三个点$u,v$，且满足$u,v$之间相距距离为$2$，则可以在$u,v$之间连一条边。问此时所有点对间最短距离和。

思路

若我们按照暴力模拟的方式，则必定超时。

考虑两点$u,v$，若它们在原图上的距离$s$为偶数，则它们在新图上的距离为$\frac{s}{2}$，若它们的距离为奇数，则它们在新图上的距离为$\frac{s+1}{2}$。

换句话说，距离之和为$$\sum ?\frac{s_{u,v}}{2}?(u\in G,v\in G)$$

这样时间复杂度就降低到了$O(n^2)$。

但是对于这道题，时间复杂度还是太高了。。。

所以，我们将式子展开一下。不难发现在$s_{u,v}$中，有一些奇数的路径多出的$\frac{1}{2}$也对答案做了贡献。考虑将这些$\frac{1}{2}$提出来。就可以发现，答案就变为：（所有路径长度之和+奇数路径个数）/2。

首先是求所有路径长度之和。我们考虑以$u$为根的子树，其大小为$s_u$，如下图：

不难发现每条边经过的次数为$s_u\times (N?s_u)$。则所有路径长度之和=$\sum s_u\times (N?s_u)(u\in G)$。所以这个可以DFS一次解决。

接下来是求奇数路径个数。考虑两点$u,v$，若点$u$在奇数层，$v$在偶数层，则两点间距离必定为奇数，所以，奇数路径个数就等于奇数层点数*偶数层点数，这东西也可以在求所有路径长度之和时顺带着做了。

注意数据可能炸int，请使用long long。

正解代码

#include<cstdio> #include<vector> #include<algorithm> using namespace std;typedef long long ll; const int Maxn=200000;int N; vector<int> G[Maxn+5]; inline void addedge(int u,int v) {
     G[u].push_back(v);G[v].push_back(u); }ll ans,cnt[3]; ll DFS(int u,int fa,int col) {
     cnt[col]++;//记录奇数层和偶数层点的个数//cnt[0]-奇数点数，cnt[1]-偶数点数ll siz=1;for(int i=0;i<G[u].size();i++) {
     int v=G[u][i];if(v==fa)continue;siz+=DFS(v,u,col==1?0:1);}ans+=siz*(N-siz);return siz; }int main() {
     #ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d",&N);for(int i=1;i<N;i++) {
     int u,v;scanf("%d %d",&u,&v);addedge(u,v);}DFS(1,0,0);printf("%lld\n",(ans+cnt[0]*cnt[1])/2);return 0; }