链接：https://ac.nowcoder.com/acm/problem/14248
来源：牛客网

Treepath
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。

输入描述: 

第一行一个数n表示点的个数；
接下来n-1行，每行两个整数x，y表示边；
保证输入数据形成一棵树；
1<=n<=100000

输出描述: 

一行一个整数表示答案。
示例1

输入

复制 3 1 2 1 3 
3
1 2
1 3

输出

复制 1 
1


求偶数长度的路径有多少条
 
首先将题目转换一下：求点数为奇数的路径有多少条

然后将奇数的路径分为，从每个结点出发向下的奇数的路径与向上的奇数路径，向上的奇数路径就可以根据 合并的思想，将每个节点作为中间节点过度一下即可：

具体使用
dp[i][1]表示从i出发，长度为奇数个点的路径数 
dp[i][0]表示从i出发 ，长度为偶数个点的路经数

转移显然：
dp[u][1]+=dp[e][0]  ///当前节点作为一个点
dp[u][0]+=dp[e][1]

中间启发合并过度节点 只需要记录在访问节点前的偶数节点个数与奇数节点个数即可：

Code： 

/*** keep hungry and calm CoolGuang!***/
//#pragma GCC optimize(2)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pp;
const ll INF=1e17;
const int maxn=3e5+6;
const int mod=20020421;
const double eps=1e-3;
inline bool read(ll &num)
{char in;bool IsN=false;
in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
ll dp[maxn][2];
ll ans=0;
vector<int>v[maxn];
void dfs(int u,int fa){
    dp[u][1]=1;
    ll a=0,b=0;
    for(int e:v[u]){
        if(e==fa) continue;
        dfs(e,u);
        dp[u][1]+=dp[e][0];
        dp[u][0]+=dp[e][1];
        ans+=dp[e][0]*a;
        ans+=dp[e][1]*b;
        a+=dp[e][0];
        b+=dp[e][1];
    }
}
int main()
{
    read(n);
    for(int i=1;i<=n-1;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,1);
    for(int i=1;i<=n;i++)
        ans+=dp[i][1];
    printf("%lld\n",ans-n);
    return 0;
}

/***
1 2 3 4 5
***/