Jisoo

这是一种叫线段树合并的东西。

为了简化，我们需要动态开点。

并且一开始为每一个节点建一个线段树，当然是动态开点的

然后合并就行了，相同的线段树节点加起来，只有一个有的就返回另一个

记一个根，并且并查集一下。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<vector>
#include<stack>
#include<algorithm>
#define int long long
using namespace std;
template<class T>inline void read(T &x)
{
    x=0;register char c=getchar();register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(f)x=-x;
}
template<class T>inline void print(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar('0'+x%10);
}
int n;
int x,y;
vector<int> v[200001];
int siz[200001];
int tot;
int ans;
int dep[2000001];
int cnt[2];
void dfs(int no,int f){
    dep[no]=dep[f]+1;
    cnt[dep[no]%2]++;
    siz[no]++;
    for(auto x=v[no].begin();x!=v[no].end();++x){
        if((*x)==f) continue;
        dfs(*x,no);
        siz[no]+=siz[*x];
    }
    return ;
}
signed main(){
    read(n);
    for(int i=1;i<n;++i){
        read(x);read(y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    for(int i=1;i<=n;++i){
        for(auto j=v[i].begin();j!=v[i].end();++j){
                if(dep[(*j)]>dep[i]){
                ans+=siz[*j]*(n-siz[*j]);
                //cout<<" "<<i<<" "<<(*j)<<endl;
                }
        }
    }
    ans+=cnt[0]*cnt[1];
    cout<<ans/2;
    return 0;
}