Sergey and Subway(CodeForces-1060E#513)(DFS计数,数学)

本文主要是介绍Sergey and Subway(CodeForces-1060E#513)(DFS计数,数学)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

前言
题目
思路
代码

前言

本题思路极为简单和巧妙！

题目

CF传送门
题目大意:
给你一个有n个节点的树,如果有原树有两点距离为2则加一条边,求修改后所有点对的距离和.
数据范围：
$2 < = n < = 200000$
样例：
$i n p u t 1$

$o u t p u t 1$

$i n p u t 2$

$o u t p u t 2$

思路

首先我们要知道不加边怎么做…
如果我们对于每个点对都进行分析的话,什么都不说, $O(n^2)$ 直接爆炸,
我们要把重点放到边上
在这里插入图片描述
如图,每一条边经过的次数就是:
$s i z [u] * (S - s i z [u])$
对于每一条边 $O (n)$ 算即可
但是加上题目条件呢？
我们可以发现,新树中两个点间距离为偶数那么直接除以二,为奇数就加1除以2,我们可以对整棵树进行黑白染色:
在这里插入图片描述
我们发现,只有异色情况距离为奇,那么答案加上黑点个数*白点个数即可,也就是加了1
最后除以二即可

代码

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<climits>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int read(){int f=1,x=0;char s=getchar();   while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}  while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}return x*f;
}
#define MAXN 200000
#define INF 0x3f3f3f3f
#define Mod int(1e9+7)
vector<int> G[MAXN+5];
int n,oe[MAXN+5],tsiz[MAXN+5];
void DFS(int u,int fa){tsiz[u]=1;int siz=G[u].size();for(int i=0;i<siz;i++){int v=G[u][i];if(v==fa) continue;oe[v]=!oe[u];//奇偶性分析DFS(v,u);//算子树大小tsiz[u]+=tsiz[v];}return ;
}
int main(){n=read();for(int i=1;i<n;i++){int u=read(),v=read();G[u].push_back(v),G[v].push_back(u);}DFS(1,0);LL ans=0,cnt=0;for(int i=1;i<=n;i++){if(oe[i]) cnt++;//计算答案ans+=1ll*tsiz[i]*(n-tsiz[i]);}ans+=cnt*(n-cnt);printf("%lld\n",ans/2);return 0;
}