Treepath

题意

给定一棵n个节点的树，问路径长度为偶数的路径数（u->v 和 v-> u只算一次）

思路

刚开始想歪了，想了好久的树形dp，没想出来，就去看题解，看了第一行题（niu）解（bi）小姐姐说是水题就没脸往下看了QAQ。后面发现可以按深度做，先dfs一遍把把每个节点所处的深度处理出来（随便取一个点为根节点）。对于同深度的两个个节点，其最短路径必然是其中一个点到这两个点的最近公共祖先，再到另一个点，是对称的，因此路径长度是偶数。对于不在同一深度的两个节点，若在同一棵子树，最短路径就是深度相减取绝对值。若不在同一子树就把深度较大的节点移动到与深度较小的节点同一深度的节点上，然后就可以当做同一深度的两个节点，其路径长度必然是偶数。通过以上分析，要得到路径为偶数的路径，只需要保证深度差为偶数就行。（记得开long long）

复杂度

代码

#include<bits/stdc++.h>

using namespace std;

int n;
const int maxn = 1e5 + 10;

long long cnt[2];
long long d[maxn];
bool vis[maxn];

vector<int> g[maxn];

void dfs(int i, int dep){
    vis[i] = 1;
    d[dep]++;
    cnt[dep & 1]++;

    for(auto v : g[i]){
        if(!vis[v]){
            dfs(v, dep + 1);
        }
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1, 0);

    long long ans = 0;
    for(int i = 0; i < n; i++){
        ans += (cnt[i & 1] - d[i])*d[i] + (d[i] - 1LL) * d[i] ;
    }
    cout << ans / 2LL << endl;
    return 0;

}