E. Sergey and Subway(思维)

• E. Sergey and Subway

题意：

给出一颗树，对他进行加边，如果三个顶点u,v,w，u连到v，v连到w，那么u和w之间加一条边。问最后每对点的距离之和。每条边权值为1

思路：

1. 先求出不加边之前每对点之间的距离和，一条边u到v，被用到的次数就是以v为根节点的树的大小sz[v](n-sz[v])次。所以求出每个点，以当前点为根节点的树的大小sz[i].对sz[i](n-sz[i])进行求和，就是不加边前的距离和。
2. 加边的话，距离为偶数的点对，距离会变成原来的一半，奇数的变成原来的一半+1，不加边前的距离和（ans）=偶数层到偶数层的点对距离和(X)+奇数层到奇数层的点对距离和(Y)+奇数到偶数的点对距离和(Z) 。X和Y必然为偶数，缩小一半，Z的奇数距离点对中的1，节省的步数就是(ANS-奇数到偶数的点对个数)/2
   ans=ans-(ans-num*(n-num))/2;

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pii;
typedef vector<int>vi;

#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define per(i,a,b) for(int i=(a);i>(b);--i)
#define de(x) cout<<#x<<"="<<x<<endl
#define dd(x) cout<<#x<<"="<<x<<" "
const int N=2e5+5;
ll sz[N];
ll num=0;
vector<int>G[N];
bool vis[N];
void dfs(int u,int deep){
    if(deep&1)num++;
    sz[u]=1;
    rep(i,0,G[u].size()){
        int v=G[u][i];
        if(!vis[v]){
            vis[v]=true;
            dfs(v,deep+1);
            sz[u]+=sz[v];
        }
    }
}
int main(){
    int n;
    cin>>n;
    int u,v;
    rep(i,1,n){
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    memset(vis,false,sizeof(vis));
    vis[1]=true;
    dfs(1,1);
    ll ans=0;
    rep(i,1,n+1){
        ans+=sz[i]*(n-sz[i]);
    }
    ans=ans-(ans-num*(n-num))/2;
    cout<<ans<<endl;
}