每日一题：Treepath

题意：

给定一棵n个节点的树，求偶数长度路径的数量。

Solution1:

考虑树的深度对距离的影响，可以发现，深度奇偶性相同的点之间的距离总是偶数。

证明：我们先将深度更大的点走到和另一个点深度相同，显然需要偶数步，然后两个点同时移动到最近公共节点，可知所用的步数是相同的，加起来也是偶数。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

int n, idx, h[N], dep[N];

struct Node {
  int to, next;
} E[N];

void add(int a, int b) { E[idx].to = b, E[idx].next = h[a], h[a] = idx++; }

void dfs(int u, int fa) {
  dep[u] = dep[fa] + 1;
  for (int i = h[u]; ~i; i = E[i].next) {
    int v = E[i].to;
    if (v == fa) continue;
    dfs(v, u);
  }
}

int main() {
  memset(h, -1, sizeof(h));
  cin >> n;
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    add(x, y);
    add(y, x);
  }
  dfs(1, 0);
  long long odd = 0, even = 0, res;
  for (int i = 1; i <= n; i++) {
    if (dep[i] & 1)
      odd++;
    else
      even++;
  }
  res = odd * (odd - 1) / 2 + even * (even - 1) / 2;
  cout << res << '\n';
  return 0;
}

solution2:

考虑树形dp。$dp[i][0/1]$ 表示从 i 出发，长度为偶数/奇数的路径数。

从子节点到父节点状态转移：

$dp[u][1] += dp[v][0]$

$dp[u][0] += dp[v][1]$

对于 $u$ 的每一个儿子 $v$，贡献即为 $dp[u][0] \times dp[v][1] + dp[u][1] \times dp[v][0]$, dfs回溯时进行合并更新即可。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
typedef long long ll;

int n, idx, h[N];
ll res, dp[N][2];

struct Node {
  int to, next;
} E[N];

void add(int a, int b) { E[idx].to = b, E[idx].next = h[a], h[a] = idx++; }

void dfs(int u, int fa) {
  dp[u][0] = 1;
  for (int i = h[u]; ~i; i = E[i].next) {
    int v = E[i].to;
    if (v == fa) continue;
    dfs(v, u);
    res += dp[v][0] * dp[u][1];
    res += dp[v][1] * dp[u][0];
    dp[u][0] += dp[v][1];
    dp[u][1] += dp[v][0];
  }
}

int main() {
  memset(h, -1, sizeof(h));
  cin >> n;
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    add(x, y);
    add(y, x);
  }
  dfs(1, 0);
  cout << res << '\n';
  return 0;
}

总结

关于树上统计问题一直是个人较怕的题目（虽然经常出现但几乎每次都不会做 T_T），树上问题往往离不开dfs，需要考虑父子节点的转移，必要时可以考虑树形dp。