文章总览：一心二用之术

这个算法其实之前写过，但是写的一塌糊涂，所以说这里重新写了。这篇文章的主要内容是点分治算法，另外会额外拓展一些点分树的内容。点分治很显然就是基于点的分支，其详细内容会在下文介绍，大体分类属于树分治。本文讲述点分治与点分树，树分治就还剩下一个边分治了，接下来是本文大纲：

  1. 点分治思想
  2. 点分治例题
  3. 点分树思想
  4. 点分树例题

算法推导：理清逃跑路线

那么还是来介绍一下点分治的概念。点分治呢其实是一种基于点在树上的分治，它基于点与树上路径的关系来快速统计一些树上路径的信息。在点分治中，路径可以分为两类：

  1. 经过当前根的。这个又可以分为端点为根或者两个端点都不为根。
  2. 不经过当前根的。

显然第一类中的第二个情况是可以通过第一个情况造成了两个链拼接而成，而不经过当前根的我们需要接下去递归处理，所以说这里是关于点分治正确性的一些简单证明。

然后我们来思考一个问题，点分治的分治逻辑是什么。因为说一般来讲树都是无根树，我们递归的顺序可以非常明显的影响到我们的复杂度。这个就不难想到是用重心了，因为重心每一次可以排除掉这棵树 $1/2$ 的大小，大大节约了我们的复杂度，这样的话点分治除去统计数据的部分，复杂度就是 $O(n\log n)$。

友情链接：

【奇技淫巧】特殊思维题的复杂度分析 | 祝馀宫

大致的思路有了，我们接下来看一下比较具体的分段实现。首先找重心什么的都不用说了，这个属于简单的部分，直接快进到点分治函数的编写思路上。

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
namespace Divide {
    int rt, sz[MaxV], mxs[MaxV];

    inline void GetSize(int u, int fa) {
        sz[u] = 1;
        for(int i = G.head(u); i; i = G.nt(i)) {
            int v = G.to(i);
            if(v == fa || vis[v]) continue;
            GetSize(v, u);
            sz[u] += sz[v];
        }
    }
    inline void GetRoot(int u, int fa, int tot) {
        mxs[u] = tot - sz[u];
        for(int i = G.head(u); i; i = G.nt(i)) {
            int v = G.to(i);
            if(v ==fa || vis[v]) continue;
            GetRoot(v, u, tot);
            mxs[u] = max(mxs[u], sz[v]);
        }
        if(mxs[u] < mxs[rt]) rt = u;
    }

    // coding something here. 
    vector<ll >dis;
    inline void GetDis(int u, int fa, ll d) {
        
    }
    inline int Calc(int u, ll base) {
        
    }

    // 初始预处理
    inline void Init() {
        GetSize(1, 0);
        rt = 0; mxs[0] = 1e9;
        GetRoot(1, 0, sz[1]);
    }
    // 点分治
    inline void Dfs(int u) {
        vis[u] = 1; ans += Calc(u, 0); // 标记 + 统计答案
        for(int i = G.head(u); i; i = G.nt(i)) {
            int v = G.to(i);
            if(vis[v]) continue;
            ans -= Calc(v, G.wt(i)); // 这里是容斥，视情况而定的
            GetSize(v, 0); // 求出每一个点的子树大小，方便计算重心
            rt = 0, mxs[0] = 1e9; 
            GetRoot(v, 0, sz[v]); // 找重心
            Dfs(rt); // 递归
        }
    }
    // 纯无聊，向这些这个玩意在主函数好看一些
    inline void Dfs() { Init(); Dfs(rt); }
};

其实也没什么难，点分治的重点还是在计算路径上，我们可以看一个题感受一下。

例题解析：都交给分身吧

题目传送门

题目大意

求一棵带边权的树上长度小于等于 $k$ 的路径数量。点的个数 $n$ 满足 $n\le 10000$。

解题思路

其实是模板题了。我们这里这样定义我们的 Calc 函数：$u$ 的子树中初始长度为 $base$ 的路径数量，因为代码编写的原因，这里的路径是可以存在起点和端点在同一个子树内的。所以说这时候我们需要排除掉这一类非法的情况，为什么这一类是非法的应该不难理解，因为这条路径的起点和端点在同一个子树内，但是又经过了这个根节点，也就是说这类情况会出现有一条树边被这个路径经过两次，这种显然是非法的。

而这一类很好排除，非法路径一定会是形如一个经过根节点的某一个儿子的路径（不要求合法）再加上这个儿子连向父亲的边，也就是说我们只需要求出这个儿子的 Calc(son, wt) 函数的结果减去即可，这里就发挥了所谓初始长度的作用。

这样就是大多数细节了，然后关于路径的统计也很简单，因为要求小于等于 $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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

typedef long long ll;
// typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

template<int N, int M>
class Graph {
    private :
        struct Edge {
            int to, nt;
            ll wt, fl, cp;
            Edge() {}
            Edge(int to, int nt, ll wt, ll cp, ll fl) : 
                to(to), nt(nt), wt(wt), cp(cp), fl(fl) {}
        }e[M];
        int hd[N], cnte;
    public :
        inline void clear() { memset(hd, 0, sizeof(hd)), cnte = 0; }
        inline void AddEdge(int u, int v, ll w = 0, ll c = 0, ll f = 0) {
            e[++cnte] = Edge(v, hd[u], w, c, f);
            hd[u] = cnte;
        }
        inline int head(int u) { return hd[u]; }
        inline int nt(int u) { return e[u].nt; }
        inline int to(int u) { return e[u].to; }
        inline ll wt(int u) { return e[u].wt; }
        inline ll& flw(int u) { return e[u].fl; }
        inline ll& cap(int u) { return e[u].cp; }
};

const int MaxV = 1e4 + 10;
const int MaxE = 2e4 + 10;

int n, K;
Graph< MaxV, MaxE >G;

inline void Input() {
    read(n, K);
    if(n == 0 && K == 0) return exit(0);
    int u, v, w;
    for(int i = 1; i < n; i++) {
        read(u, v, w);
        G.AddEdge(u, v, w);
        G.AddEdge(v, u, w);
    }
}

ll ans;
int vis[MaxV];

namespace Divide {
    int rt, sz[MaxV], mxs[MaxV];

    inline void GetSize(int u, int fa) {
        sz[u] = 1;
        for(int i = G.head(u); i; i = G.nt(i)) {
            int v = G.to(i);
            if(v == fa || vis[v]) continue;
            GetSize(v, u);
            sz[u] += sz[v];
        }
    }
    inline void GetRoot(int u, int fa, int tot) {
        mxs[u] = tot - sz[u];
        for(int i = G.head(u); i; i = G.nt(i)) {
            int v = G.to(i);
            if(v ==fa || vis[v]) continue;
            GetRoot(v, u, tot);
            mxs[u] = max(mxs[u], sz[v]);
        }
        if(mxs[u] < mxs[rt]) rt = u;
    }

    // coding something here. 
    vector<ll >dis;
    inline void GetDis(int u, int fa, ll d) {
        dis.push_back(d);
        for(int i = G.head(u); i; i = G.nt(i)) {
            int v = G.to(i);
            if(v == fa || vis[v]) continue;
            GetDis(v, u, d + G.wt(i));
        }
    }
    inline int Calc(int u, ll base) {
        dis.clear();
        GetDis(u, -1, base);
        sort(dis.begin(), dis.end());
        int ans = 0, l = 0, r = dis.size() - 1;
        while(l < r) {
            if(dis[l] + dis[r] <= K) {
                ans += r - l;
                l++;
            }
            else r--;
        }
        return ans;
    }

    inline void Init() {
        GetSize(1, 0);
        rt = 0; mxs[0] = 1e9;
        GetRoot(1, 0, sz[1]);
    }
    inline void Dfs(int u) {
        vis[u] = 1; ans += Calc(u, 0);
        for(int i = G.head(u); i; i = G.nt(i)) {
            int v = G.to(i);
            if(vis[v]) continue;
            ans -= Calc(v, G.wt(i));
            GetSize(v, 0);
            rt = 0, mxs[0] = 1e9;
            GetRoot(v, 0, sz[v]);
            Dfs(rt);
        }
    }
    inline void Dfs() { Init(); Dfs(rt); }
};

inline void Work() {
    Divide::Dfs();
    printf("%lld\n", ans);
}

inline void Clear() {
    G.clear();
    ans = 0;
    memset(vis, 0, sizeof(vis));
}

int main() {
    int T = -1;
    while(T--) {
        Input();
        Work();
        Clear();
    }
    return 0;
}

算法拓展：偷懒的新方法

然后拓展一个知识点，点分树。点分树是基于点分治对于树的重新构造。其大致思想是对于点分治的递归顺序，把原树按照这个顺序建立成另一棵树，然后经行处理。

上面也说过了，由于按照重心分治每一次都至少排掉 $1/2$ 的节点，然后这个点分树的深度就是 $\log n$ 的，在这样的树上面可以大力暴力，因为很多树上暴力都是与深度有关的，这样就可以大大滴优化复杂度。

点分树的作用在于处理一些与原树形态无关的带修改问题，因为这样重构后的树几乎与原树没有任何关系。除了有一个性质，就是说：点分树上两点的 LCA 一定在这两点在原树上的路径上。

拓展例题：快是第一奥义

这个的例题也有，但是我好像写过了来着

友情链接：

【拾题杂谈】LuoguP6329 震波 | 祝馀宫

其实说实话这个点分治和点分树还是非常灵活的算法，我觉得升值能赶得上 DP 这一类问题，它的考点主要在于对于这个算法的理解，在各种细节的位置进行修改即可。

算法实战：呼呼大睡时间

查看相关算法标签喵！

参考资料（以下排名不分先后）