时间限制：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
输出
1
分析： 没多想就 往DP上想去了，从最底层往上DP，odd[now] 表示 以now为终点的所有路径中有多少路径长度为奇数，even[now]表示以now为终点的所有路径中有多少路径长度为偶数【注意now-now这也算是一个偶数长度的路径】。然后就这样写，算了不详细解释了。
看别人写的黑白染色的方法思路更明确 ，还是看那个吧。
首先贴个我的DP代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int MAXN = 100000+11 ;vector < int > ve[MAXN];
int odd[MAXN],even[MAXN];
void init(int n){for(int i=0;i<=n;i++){ve[i].clear();odd[i]=even[i]=0;}
}
LL ans;
void DFS(int now,int pre){if(ve[now].size()==1&&now!=1){even[now]=1;return ;}for(int i=0;i<ve[now].size();i++){int v=ve[now][i]; if(v==pre) continue;DFS(v,now);}for(int i=0;i<ve[now].size();i++){int v=ve[now][i]; if(v==pre) continue;ans+=odd[v];odd[now]+=even[v];even[now]+=odd[v];}even[now]++;for(int i=0;i<ve[now].size();i++){int v=ve[now][i]; if(v==pre) continue;for(int j=i+1;j<ve[now].size();j++){int u=ve[now][j]; if(u==pre) continue;ans+=(LL)odd[v]*odd[u];ans+=(LL)even[v]*even[u];}}
}int main(){int n;while(~scanf("%d",&n)){init(n);int m = n-1;while(m--){int x,y;cin>>x>>y;ve[x].push_back(y);ve[y].push_back(x);}ans=0; DFS(1,-1);// for(int i=1;i<=n;i++) printf("odd %d even %d \n",odd[i],even[i]);printf("%lld\n",ans);}
return 0;
}/*5 1 2 2 3 3 4 4 5*/
分析二： 别人的题解，既然路径长度为偶数，那么一定是偶数的路径长度一定和偶数的路径长度的连起来，奇数长度的和奇数长度连起来。我们将树进行黑白染色，这样所有黑色点任意组成的所有路径一定都是偶数，所有 白色的点任意组成的所有路径也一定都是偶数。
代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int MAXN = 100000+11 ;vector < int > ve[MAXN];
void init(int n){for(int i=0;i<=n;i++){ve[i].clear();}
}
bool color[MAXN];
void DFS(int now,int pre,int co){color[now]=co;for(int i=0;i<ve[now].size();i++){int v=ve[now][i];if(v==pre) continue;DFS(v,now,!co);}
}int main(){int n;while(~scanf("%d",&n)){init(n);int m = n-1;while(m--){int x,y;cin>>x>>y;ve[x].push_back(y);ve[y].push_back(x);}DFS(1,-1,1);LL a=0,b=0;for(int i=1;i<=n;i++)if(color[i]) a++;else b++;printf("%lld\n",a*(a-1)/2+b*(b-1)/2);}
return 0;
}/*5 1 2 2 3 3 4 4 5*/