Treepath

题意:树中长度路径为偶数的路径数，不能重复

分析：

首先 树中点x到点y的距离 =dep[x]+dep[y]-2*dep[LCA(x,y)]

首先可以发现，2*dep[LCA(x,y)]对奇偶性无影响
那么就剩下dep[x]和dep[y]

所以我们只需要求出深度为奇数的个数和偶数的个数

然后奇偶性相同的两两组合就是一种情况

深度为奇数个数：a
深度为偶数个数：b

答案=a(a-1)/2+b(b-1)/2

code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>
#include <cassert>

using namespace std;

typedef long long ll;

const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

const int N=100000+100; 

int head[N],tot;
int dep[N];
int n;
int x,y;
int f[N];

struct Edge
{
    int e;
    int to;
}edge[N<<1];

void add_edge(int u,int v)
{
    tot++;
    edge[tot].e=v;
    edge[tot].to=head[u];
    head[u]=tot;
}

void dfs(int u,int fa)
{
    for(int i=head[u];i!=0;i=edge[i].to)
    {
        int v=edge[i].e;
        if(v==fa)continue;
        dep[v]=dep[u]+1;
        dfs(v,u);
    }
}


int main()
{
    scanf("%d",&n);
    for(int i=0;i<n-1;i++)
    {
        scanf("%d%d",&x,&y);
        add_edge(x,y);
        add_edge(y,x);
    }
    dfs(1,0);
//    for(int i=1;i<=n;i++)
//    {
//        printf("节点%d的深度为%d\n",i,dep[i]);
//    }
    int s1=0;
    int s2=0;
    for(int i=1;i<=n;i++)
    {
        if(dep[i]%2==0)
        {
            s1++;
        }
        else
        {
            s2++;
        }
    }
    ll ans=1ll*(s1*1ll-1)*s1*1ll/2+1ll*(s2*1ll-1)*s2*1ll/2;
    printf("%lld\n",ans); 
    return 0;
}