点分治学习笔记

头图是淀粉质。

淀粉质用于处理一系列有关路径的问题，问题需要有能够根据根节点求出的信息高效的求出（注意，不是全部答案，只是有关根节点的路径）答案的性质。

一般将路径分类：

1. 经过根节点的（含端点之一是根节点的），这类立即处理。
2. 不经过根节点的，这类再分治处理。

如何确定找那些信息，该怎么高效的找，获得信息之后如何高效求答案，这都是我们要考虑的问题。

算法本身其实很暴力，就是找一个根，暴力扫一遍，再分治子树，最终每个点都会作为根节点求一次其对应的答案。

由于重心拥有将树分为不大于原树大小二分之一的若干棵子树的性质，所以我们处理一棵树时，选择其重心为根，这样最多分治 次，拥有优秀的复杂度。

参考伪代码实现：

int getcentroid(int u)
{
    // 通过某些方式寻找重心（例如 dfs）
    return centroid;
}

void dfs(int u)
{
    // 获取以 u 为根节点有关的信息
    // ...
}

bool vis[];

void solve(int u) // 当前在处理 u 子树
{
    int rt = getcentroid(u);
    vis[rt] = 1; // 标记，该点已被处理，不应被在接下来处理子树时被包含
    for(int v : grh[rt])
    {
        if(/* 判断是否是接下来要处理的子树 */)
            solve(v);
    }
    dfs(u);
    // ...（根据 dfs 获得的信息求答案）
    vis[rt] = 0;
}

例题：

洛谷 P4178 Tree

题目描述:

给定一棵 个节点的树，每条边有边权，求出树上两点距离小于等于 的点对数量。

保证：

• 。
• 。
• 。
• 。

样例输入：

7
1 6 13 
6 3 9 
3 5 7 
4 1 3 
2 4 20 
4 7 2 
10

样例输出：

5

对应前面讲的：

• 这是一道有关路径的问题，且路径可以像上面那样分类。
• 当我们知道其他点到根节点的路径长度时，可以通过排序加双指针 地求答案，这足够高效。

然后代码：

#include <bits/stdc++.h>
#define nmf(i, s, e) for (int i = s; i <= e; i++)
#define ref(i, s, e) for (int i = s; i >= e; i--)
namespace FastIO
{
    template <typename T>
    inline void read(T &x)
    {
        short neg = 1;
        char ch;
        while (ch = getchar(), !isdigit(ch))
            if (ch == '-')
                neg = -1;
        x = ch - '0';
        while (ch = getchar(), isdigit(ch))
            x = (x << 3) + (x << 1) + (ch ^ '0');
        x *= neg;
    }
    template <typename T, typename... Args>
    inline void read(T &x, Args &...args)
    {
        read(x);
        read(args...);
    }
    template <typename T>
    inline void read(T *begin, T *end)
    {
        unsigned len = end - begin;
        for (unsigned i = 0; i < len; i++)
            read(*(begin + i));
    }
    template <typename T>
    inline void write(T x)
    {
        if (x < 0)
            putchar('-'), x = -x;
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
    template <typename T, typename... Args>
    inline void write(T x, Args... args)
    {
        write(x);
        putchar(' ');
        write(args...);
    }
    template <typename T>
    inline void write(T *begin, T *end)
    {
        unsigned len = end - begin;
        for (unsigned i = 0; i < len; i++)
            write(*(begin + i)), putchar(' ');
    }
}
using namespace FastIO;
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
int n, k;
vector<pair<int, int>> grh[40004];
bool vis[40004];
int sz[40004];
void getsz(int u, int fa)
{
    sz[u] = 1;
    for (auto e : grh[u])
    {
        int v = e.first;
        if (v == fa || vis[v])
            continue;
        getsz(v, u);
        sz[u] += sz[v];
    }
}

int root;
int centroid;
void find(int u, int fa)
{
    if (sz[u] * 2 >= sz[root])
        centroid = u;
    for (auto e : grh[u])
    {
        int v = e.first;
        if (v == fa || vis[v])
            continue;
        find(v, u);
    }
}

int getcentroid(int u) // 找中心
{
    root = u;
    getsz(u, 0);
    find(u, 0);
    return centroid;
}

void add(int u, int fa, int d, vector<int> &goal) // 获取信息
{
    goal.emplace_back(d);
    for (auto e : grh[u])
    {
        int v = e.first;
        if (v == fa || vis[v])
            continue;
        int w = e.second;
        add(v, u, d + w, goal);
    }
}

LL count(vector<int> &a) // 用信息计算答案
{
    sort(a.begin(), a.end());
    LL ret = 0;
    int r = a.size() - 1;
    nmf(l, 0, a.size() - 1)
    {
        while (r >= 0 && a[l] + a[r] > k)
            r--;
        if (r >= l)
            ret += r;
        else
            ret += r + 1;
    }
    return (ret >> 1);
}

LL ans;

void solve(int u) // 点分治
{
    int rt = getcentroid(u);
    vis[rt] = 1;
    for (auto e : grh[rt])
    {
        int v = e.first;
        if (vis[v])
            continue;
        solve(v);
    }
    vector<int> a(1, 0);
    for (auto e : grh[rt])
    {
        int v = e.first;
        if (vis[v])
            continue;
        vector<int> va;
        add(v, rt, e.second, va);
        ans -= count(va);
        a.insert(a.end(), va.begin(), va.end());
    }
    ans += count(a);
    vis[rt] = 0;
    return;
}
signed main()
{
    read(n);
    nmf(i, 2, n)
    {
        int ui, vi, wi;
        read(ui, vi, wi);
        grh[ui].emplace_back(vi, wi);
        grh[vi].emplace_back(ui, wi);
    }
    read(k);
    solve(1);
    write(ans);
    return 0;
}

发现跟上面伪代码结构还是很相似的吧？