点分治 1

问题描述:

        给定一棵有 n 个点的树，查询树上距离为 k 的点对是否存在

输入样例	输出样例
2 1 1 2 2 2	AYE

静态点分布

#include <iostream>
#include <cstring>
#include <unordered_set>
using namespace std;

const int N = 1e4 + 10, M = N << 1;
int n, m;
int h[N], e[M], ne[M], w[M], idx;
int sz[N], dist[N], pd;
bool vis[N];
int query[110];
bool res[110];
unordered_set<int> se;                             //集合

void add(int a, int b, int c) {                    //加边
  e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int get_sz(int u, int from) {                      // 返回以 u 为根的子树大小，父节点是from
  if (vis[u]) return 0;
  sz[u] = 1;
  for (int i = h[u]; ~i; i = ne[i]) {
    int v = e[i];
    if (v != from) sz[u] += get_sz(v, u);
  }
  return sz[u];
}

bool get_wc(int u, int from, int tot, int &wc) {   // 求目标子树的重心
  int ms = 0;
  for (int i = h[u]; ~i; i = ne[i]) {
    int v = e[i];
    if (v == from || vis[v]) continue;              // 父节点或已经遍历过
    if (get_wc(v, u, tot, wc)) return true;
    ms = max(ms, sz[v]);                            // 该点重心时连通块里最大的节点数量
  }
  ms = max(ms, tot - sz[u]);
  if (ms <= tot / 2) {                              //判断节点是否是重心
    wc = u;                                         //更新重心节点
    return true;                                    //是重心
  }
  return false;                                     //不是重心
}

void get_dist(int u, int from, int d, int &pd) {    //每个节点到重心的距离
  if (vis[u]) return;
  // 将距离存进dist数组中
  dist[pd++] = d;
  for (int i = h[u]; ~i; i = ne[i]) {                //遍历树的节点
    int v = e[i];
    if (v != from) get_dist(v, u, d + w[i], pd);     //非父节点向下递归添加到d
  }
}

void dfs(int u) {
  if (vis[u]) return;                                //剪枝：标记的跳过
  get_wc(u, -1, get_sz(u, -1), u);                   //更新u重心
  vis[u] = true;                                     //标记已走过
  se.clear();
  for (int i = h[u]; ~i; i = ne[i]) {                // 遍历树节点
    int v = e[i];
    pd = 0;                                          // 路径序号初始化
    get_dist(v, -1, w[i], pd);
    for (int j = 1; j <= m; j++) {                   //遍历查询
      if (res[j]) continue;
      int k = query[j];                              //拿出比较的权值
      // 看一下从重心出发的路径有没有长度为k的
      for (int l = 0; l < pd; l++)
        if (k >= dist[l] && se.count(k - dist[l])) { //当前路径+历史路径
          res[j] = true; //找到了
          break;
        }
    }
    for (int l = 0; l < pd; l++) se.insert(dist[l]); //储存历史路径
  }
  // 看一下从重心出发的路径有没有长度为k的
  for (int j = 1; j <= m; j++) {
    if (res[j]) continue;                            //剪枝：跳过已找到的
    if (se.count(query[j])) res[j] = true;           //在集合中直接寻找
  }

  // 递归处理子问题
  for (int i = h[u]; ~i; i = ne[i]) dfs(e[i]);       //遍历每个节点里的重心，直到找到所有的路径组合
}

int main() {
  memset(h, -1, sizeof h);                            // 初始化
  scanf("%d%d", &n, &m);                              // 节点数量、询问次数
  for (int i = 1; i < n; i++) {                       // 建树
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    add(a, b, c), add(b, a, c);
  }

  for (int i = 1; i <= m; i++) scanf("%d", &query[i]); //离线
  dfs(1);
  for (int i = 1; i <= m; i++)                         //遍历输出查询结果
    res[i] ? puts("AYE") : puts("NAY");                
}

笔记：和上一道题 Tree 基本上是一样，一个是小于 k 的所有路径，一个是查找等于 k 的路径。点分治是统计树上路径的高效算法，只查询不修改是静态树，加上修改的是动态树

版权声明：

本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。本文链接：https://blog.csdn.net/qq_46105170/article/details/125592740