题解 - 多树

题目描述

给定 $n$ 和 $k$ 棵有 $n$ 个点的树。对于每个点对 $(i,j)$ ，求出其在每棵树上的路径经过的点（含端点）的交集大小。

数据范围: $1 \leq n, k \leq 500$ 时间限制: $2.000s$

题解

首先明白一个性质：对于某一棵树，考虑 $x$ 在 $(u, v)$ 路径上的充要条件：$dis(u,x) + dis(x,v) = dis(u,v)$。

如果 $dis(u,x)+dis(x,v)\gt dis(u,v)$ 那么 $x$ 就不在 $(u, v)$ 的路径上。

那么判断这么多棵树，逐次枚举肯定不行。考虑前面的性质，可以将所有树上任意两点距离累加，最后 $\mathcal{O}(n^3)$枚举距离判断，即可通过此题。

细节：既然是一颗树，求距离就用dfs，不要用那个n^3的什么b Floyd了

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int N = 510;
int sum[N][N];
int dep[N];
vector<int> G[N];
int n, k;
void init() {
  for(int i = 0; i <= n; i++) {
    G[i].clear();
  }
  int u, v;
  for(int i = 2; i <= n; i++) {
    scanf("%d%d", &u, &v);
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }
}
void dfs(int pos, int fa) {
  dep[pos] = dep[fa] + 1;
  for(auto i : G[pos]) {
    if(i == fa) continue;
    dfs(i, pos);
  }
}
int main()
{
  // freopen("trees.in", "r", stdin);
  // freopen("trees.out", "w", stdout);
  scanf("%d%d", &n, &k);
  for(int i = 1; i <= k; i++) {
    init();
    for(int j = 1; j <= n; j++) {
      dfs(j, 0);
      for(int k = 0; k <= n; k++) {
        sum[j][k] += dep[k] - 1;
      }
    }
  }
  int ans = 0;
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++) {
      ans = 0;
      for(int k = 1; k <= n; k++) {
        if(sum[i][k] + sum[k][j] == sum[i][j]) ans++;
      }
      printf("%d ", ans);
    }
    printf("\n");
  }
  return 0;
}