题目描述
给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。
输入描述:
第一行一个数n表示点的个数；
接下来n-1行，每行两个整数x，y表示边；
保证输入数据形成一棵树；
1<=n<=100000
输出描述:一行一个整数表示答案。
#include<bits/stdc++.h>
using namespace std;const int N = 100005;
int num[2],vis[N];
vector<int>G[N];void dfs(int u,int cnt)
{num[cnt]++;//0或1，记录奇偶数节点vis[u] = 1;//去过则为1for(int i=0;i<G[u].size();i++)//在此节点连接节点没遍历完之前{int v=G[u][i];//v是根节点连接的子节点if(vis[v])continue;dfs(v,1-cnt);//就是cnt和1-cnt差别对待奇偶数}
}int main()
{int n,u,v;scanf("%d",&n);for(int i = 0;i < n-1;i++){scanf("%d%d",&u,&v);G[u].push_back(v);//爹连儿子G[v].push_back(u);//儿子连爹}dfs(1,0);long long sum = num[0]*(num[0]-1ll)/2 + num[1]*(num[1]-1ll)/2;printf("%lld\n",sum);return 0;
}
思路：很多题解都说了 找奇数奇数或者偶数偶数，我一直卡在怎么理解题意和代码了。。
首先题意：n个节点，每行输入xy表示两个节点相连，比如n=3,1 2,1 3，表示一共三个节点，一个爹节点1和左儿子2右儿子3,12相连13相连，其中按层数来看的话，分为一层和二层，也就是说一个奇数点两个偶数点或者理解成一个偶数两个奇数也行，然后排列组合C(2,2)，所以有一条。
再看代码，那就是怎么找偶数点和奇数点的问题了，画成图的话很好理解，一个一个看就完了，但程序处理的话得清楚地让计算机把奇数层偶数层分开看待记录。首先我们在输入数据的时候就把爹连着儿子，儿子连着爹，起初我不理解为什么儿子也要连爹，明明直接爹连着儿子就可以在dfs时候一点点遍历全部节点，但提交过不了全部数据，所以我觉得应该是输入数据时候也没说一定谁是爹谁是儿子，所以双面处理一下，反正去过这个节点以后会更新vis数组，也不会多很多处理。。。
核心就是num这个数组，0和1，一个偶数一个基数，如果dfs传入0，那儿子就储存在1，如果传入1，那儿子就储存在0，而0和1的判断可以直接1-cnt自动判断。
感谢观看