点分治

【模板】点分治 1

给定一棵有 \(n\) 个点的树，询问树上距离为 \(k\) 的点对是否存在。

视频讲解（来源：董晓算法）

实现 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 10, MAXM = 1e2 + 10, MAXK = 1e7 + 10, inf = numeric_limits<int>::max();
struct edge
{
    int v, w, nxt;
} E[MAXN << 1];
int n, m, qk[MAXM], rt, rtsiz, siz[MAXN], dis[MAXN], dd[MAXN], head[MAXN], sum, ddcnt;
bool vis[MAXN], tf[MAXK * 10], yes[MAXM];
queue<int> tag;
void add_edge(int u, int v, int w)
{
    static int edge_cnt = 0;
    E[++edge_cnt] = {v, w, head[u]};
    head[u] = edge_cnt;
}
void calcsiz(int u, int f)
{
    int mxsiz = 0;
    siz[u] = 1;
    for (int i = head[u]; i; i = E[i].nxt)
    {
        int v = E[i].v, w = E[i].w;
        if (v ^ f && !vis[v])
        {
            calcsiz(v, u);
            siz[u] += siz[v];
            mxsiz = max(mxsiz, siz[v]);
        }
    }
    mxsiz = max(mxsiz, sum - siz[u]);
    if (mxsiz < rtsiz)
    {
        rtsiz = mxsiz;
        rt = u;
    }
}
void calcdis(int u, int f)
{
    dd[++ddcnt] = dis[u];
    for (int i = head[u]; i; i = E[i].nxt)
    {
        int v = E[i].v, w = E[i].w;
        if (v ^ f && !vis[v])
        {
            dis[v] = dis[u] + w;
            calcdis(v, u);
        }
    }
}
void dfs(int u, int f)
{
    vis[u] = true;
    tag.push(0);
    tf[0] = true;
    for (int i = head[u]; i; i = E[i].nxt)
    {
        int v = E[i].v, w = E[i].w;
        if (v ^ f && !vis[v])
        {
            dis[v] = w;
            calcdis(v, u);
            for (int k = 1; k <= ddcnt; k++)
                for (int j = 1; j <= m; j++)
                    if (dd[k] <= qk[j]) yes[j] |= tf[qk[j] - dd[k]];
            for (int k = 1; k <= ddcnt; k++)
                if (dd[k] < MAXK) tag.push(dd[k]), tf[dd[k]] = true;
            ddcnt = 0;
        }
    }
    while (tag.size()) tf[tag.front()] = false, tag.pop();
    for (int i = head[u]; i; i = E[i].nxt)
    {
        int v = E[i].v, w = E[i].w;
        if (v ^ f && !vis[v])
        {
            sum = siz[v];
            rtsiz = inf;
            calcsiz(v, u);
            dfs(rt, u);
        }
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i < n; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    for (int i = 1; i <= m; i++) cin >> qk[i];
    sum = n;
    rtsiz = inf;
    calcsiz(1, -1);
    dfs(rt, -1);
    for (int i = 1; i <= m; i++) cout << (yes[i] ? "AYE" : "NAY") << endl;
    return 0;
}