Treepath---简单dfs or 基础dsu on tree

方法一------简单dfs：
dep表示深度，lca表示最近公共祖先
对于两个点u和v，u到v的路径长度是dep[u] + dep[v] - 2 x dep[lca(u,v)]
很显然 2 x dep[lca(u,v)] 一定是个偶数，所以，要想路径也为偶数，那么dep[u]和dep[v]一定是同为奇数或者同为偶数，所以，只要是深度奇偶性相同的两个点，肯定可以组成一条路径。

由于u->v和v->u只算一次，显然，就是在奇数深度节点中任意取两个，在偶数深度节点中任意取两个，那么就是组合数了，我们只需要求出以任意节点为根，计算深度奇数节点个数cnt1和深度偶数节点个数cnt2即可，答案是cnt1 x (cnt1-1) / 2 + cnt2 x (cnt2-1) / 2;

代码十分简单

#include <cctype>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
const int maxn=1e5+10;
int dep[maxn];
int Head[maxn],tot;
long long ans,cnt1,cnt2;
struct edge {
    int to,Next;
}Edge[maxn<<1];
void add(int from, int to) {
    Edge[tot]={to,Head[from]};
    Head[from]=tot++;
    Edge[tot]={from,Head[to]};
    Head[to]=tot++;
}
void dfs(int u, int fa) {
    dep[u]=dep[fa]+1;
    if (dep[u]%2) cnt1++;
    else cnt2++;
    for (int i=Head[u]; ~i; i=Edge[i].Next) {
        int v=Edge[i].to;
        if (v==fa) continue;
        dfs(v,u);
    }
}
int main() {
    memset(Head,-1,sizeof(Head));
    int n;
    scanf("%d",&n);
    for (int i=1; i<n; i++) {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    dfs(1,0);
    ans=cnt1*(cnt1-1)/2+cnt2*(cnt2-1)/2;
    printf("%lld\n",ans);
    return 0;
}

方法二-------dsu on tree
给自己加难度就用这方法就行了（滑稽）

题意转换求每个节点的子树中路径长度为偶数的数量的总和
看到子树问题，而且是树，可以想想dsu on tree，先划分重链，然后暴力emmm....
直接看代码吧，其实没什么细节，对于每个节点的子树，也是奇+奇，偶+偶这种处理

#include <cctype>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
const int maxn=1e5+10;
int sz[maxn],Son[maxn],dep[maxn];
int Head[maxn],cnt[maxn],tot;
long long ans;
struct edge {
    int to,Next;
}Edge[maxn<<1];
void add(int from, int to) {
    Edge[tot]={to,Head[from]};
    Head[from]=tot++;
    Edge[tot]={from,Head[to]};
    Head[to]=tot++;
}
void dfs(int u, int fa) {
    int Mx=0;
    sz[u]=1;
    dep[u]=dep[fa]+1;
    for (int i=Head[u]; ~i; i=Edge[i].Next) {
        int v=Edge[i].to;
        if (v==fa) continue;
        dfs(v,u);
        sz[u]+=sz[v];
        if (sz[v]>Mx) {
            Mx=sz[v];
            Son[u]=v;
        }
    }
}
void Add(int u, int fa, int val) {
    cnt[dep[u]%2]+=val;
    for (int i=Head[u]; ~i; i=Edge[i].Next) {
        int v=Edge[i].to;
        if (v==fa) continue;
        Add(v,u,val);
    }
}
void calc(int u, int fa) {
    ans+=cnt[dep[u]%2];
    for (int i=Head[u]; ~i; i=Edge[i].Next) {
        int v=Edge[i].to;
        if (v==fa) continue;
        calc(v,u);
    }
}
void solve(int u, int fa, int val) {
    for (int i=Head[u]; ~i; i=Edge[i].Next) {
        int v=Edge[i].to;
        if (v==fa||v==Son[u]) continue;
        solve(v,u,0);
    }
    if (Son[u]) solve(Son[u],u,1);
    for (int i=Head[u]; ~i; i=Edge[i].Next) {
        int v=Edge[i].to;
        if (v==fa||v==Son[u]) continue;
        calc(v,u);
        Add(v,u,1);
    }
    ans+=cnt[dep[u]%2];
    cnt[dep[u]%2]++;
    if (!val) {
        Add(u,fa,-1);
    }
}
int main() {
    memset(Head,-1,sizeof(Head));
    int n;
    scanf("%d",&n);
    for (int i=1; i<n; i++) {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    dfs(1,0);
    solve(1,0,0);
    printf("%lld\n",ans);
    return 0;
}