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

前言

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

题目

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

4 1 2 1 3 1 4 

$output1$

6 

$input2$

4 1 2 2 3 3 4 

$output2$

7 

思路

首先我们要知道不加边怎么做…
如果我们对于每个点对都进行分析的话,什么都不说,$O(n^2)$直接爆炸,
我们要把重点放到边上

如图,每一条边经过的次数就是:
$siz[u]?(S?siz[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; }