Solution
記得寒假?？陀械李}就是這道題的擴(kuò)展，好像是求路徑數(shù)目+博弈論。

表示以 i 為根的子樹(shù)到 i 的距離為偶數(shù)/奇數(shù)的數(shù)目。
那么在dfs過(guò)程中，以 u 為根且子結(jié)點(diǎn)為 v 對(duì)答案的貢獻(xiàn)是:

(子結(jié)點(diǎn)與父節(jié)點(diǎn)距離相差1，所以應(yīng)操作不同奇偶性)
當(dāng)然遍歷完也需要把 v 的路徑數(shù)合并到 u里面去:

Code

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
void put1(){ puts("YES") ;}void put2(){ puts("NO") ;}void put3(){ puts("-1"); }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a =
(a*a)%p;b >>= 1;}return ans%p;}
const int mo=998244353; const int mod=1000000007;

const int manx=1e5+5;

vector<ll>g[manx];
ll ans;  ll dp[manx][2];

void dfs(ll u,ll pre){
    dp[u][0]=1;
    for(auto v: g[u]){
        if(v==pre) continue;
        dfs(v,u);
        ans+=dp[v][0]*dp[u][1];
        ans+=dp[v][1]*dp[u][0];
        dp[u][0]+=dp[v][1];
        dp[u][1]+=dp[v][0];
    }
}

int main(){
    ll n=read();
    for(int i=1;i<n;i++){
        ll u=read(),v=read();
        g[u].pb(v); g[v].pb(u);
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}