题解 | #Treepath#

结论

奇数加奇数等于偶数

偶数加偶数等于偶数

奇数加偶数等于奇数

我们一遍dfs求出有多少个节点到根的距离为奇数，有多少个节点到根的距离为偶数

若节点到根的距离为偶数，有两种情形

情形1：以根作为其中一个端点

情形二：任选二个节点连成路径

若节点到根的距离为奇数

直接任选二个节点连成路径即可

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxm 100010
struct node{
    ll c1,c2;
}a[maxm];
ll res;
vector<int>G[maxm];
void dfs(int u,int pr){
    if(G[u].size()==1)return;
    for(int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if(v==pr) continue;
        dfs(v,u);
        if(G[v].size()==1){
            a[u].c1++;
        }
        else {
            a[u].c1+=a[v].c2+1;
            a[u].c2+=a[v].c1;
        }
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n-1;i++){
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1,0);
    ll res=a[1].c1*(a[1].c1-1)/2+a[1].c2*(a[1].c2-1)/2+a[1].c2;
    cout<<res;
    return 0;
}