NC14248

题意

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

思路

DFS 树 数据结构
这道题和CF1339D十分相像，有兴趣的可以做一下。

把题意转化为给你一颗n个结点的树，树上所有的边权值为1，求树上任意两点距离为偶数的点的个数。
问题就转化为了如何获取树上任意两点的距离是否为偶数呢？
图论相关的问题离不开画图，所以我们简单画个图。
受CF1339D给我的启发，无根树可以找一个根先固定，而根如果找任意点会带来讨论的麻烦，所以找一个叶子节点最合适不过。
令任意一片叶子为根节点，并及以叶子结点为1号点，加上其深度扩展其他点，其之间的距离差就为其标记的差的绝对值。
在这里插入图片描述
重要性质：距离为偶数的点节点标记的奇偶性相同。
好了我们现在找任意一片叶子结点进行dfs，分别记录节点为偶数的个数和奇数的个数。（初始化为-1，表示一个奇数或偶数的点出现是不会存在偶数边的，必须要有一对）
任意两个点就是

扩展小技巧：

CF里偷学Div1的大佬们的写法，如果只判断奇偶性的话我们其实还可以令其节点为1或者0，然后进行异或即可。
如上图如果按照异或来就是：
图片说明
只需要将代码中的dfs(c,u,d+1)改为dfs(c,u,d^1)即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1e5 + 5;

vector<int>G[N];
ll n,cnt=-1,tot=-1;

void dfs(int u,int fa,int d){
    if(d&1) cnt++;
    else tot++;
    for(auto c:G[u]){
        if(c==fa) continue;
        dfs(c,u,d+1);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        if(G[i].size()==1) {dfs(i,-1,1);break;}
    }
    cout<<(cnt+1)*cnt/2+(tot+1)*tot/2<<'\n';
    return 0;
}