学习笔记

淀粉质（没有淀粉树）

点分治

序列上的操作可以用很多方式维护，线段树树状数组平衡树啥的，但是如果毒瘤出题人把序列搬到了树上，则需要一些奇妙方法。一般有两种（好几种？）方法：

  1. 树链剖分，把树上路径转化成 dfn 序上的多段进行操作。
  2. LCT，不多说，目前只会板子，没搞太懂。
  3. 点分治，这个是不用把树转化成序列的，而是将树上统计（一般为统计）进行一个分治。
  4. …

接下来重点讲解第三种。

概述

在统计某类符合要求的路径数目时，可以将这种路径分为 2 类：

  1. 在根节点的各个儿子节点的子树内，不经过根节点。
  2. 经过当前选择的根节点。

对于第一种情况，我们可以直接把它分治到各个儿子节点的子树中，让它们自己去统计。

而对于第二种情况，我们可以把一条路径拆成两部分：到根节点和从根节点出发。这样每颗子树内部统计到根节点的路径，最后再合并即可。

时间复杂度分析

这块也是我这个蒟蒻刚刚稍微想明白了一点的

每次 dfs 一遍，差不多每经过一层会把整棵树遍历一遍，于是时间复杂度就取决于层数的多少。

当遇到数据构造成一条链时，时间复杂度可以卡到 O(n2)O(n^2)，不能承受，因此我们需要尽可能减少树的层数，于是每次递归之前先找一下子树的重心，从重心再开始点分治，这样时间复杂度就能达到 O(nlog⁡n)O(n\log n)。

例题

P3806 【模板】点分治1

本题要统计树上是否存在距离为 kk 的点对，我们可以把一条路径 (u,v)(u,v) 拆成 (u,root)(u, root) 和 (root,v)(root, v)，如果我们已经有了 distu,rootdist_{u, root}，就可以在一个桶里查找是否存在一条路径 (root,v)(root, v) 使得 distroot,v=k−distu,rootdist_{root, v} = k - dist_{u, root}。

同时向下递归之前要清空桶，这里不能直接 memset，会炸掉，于是用一个队列记录有多少点被改变过，最后只把这些点变为 0 即可。

代码：

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int n, m, k;
int h[N], e[N], w[N], ne[N], idx;
int dist[N];
int siz[N], maxsiz[N];
int q[N];
bool tf[N * 10];
bool vis[N], res[N];
int rt;

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

void calc_siz(int u, int fa, int sz)
{
    siz[u] = 1;
    maxsiz[u] = 0;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == fa || vis[j]) continue;
        calc_siz(j, u, sz);
        siz[u] += siz[j];
        maxsiz[u] = max(maxsiz[u], siz[j]);
    }
    maxsiz[u] = max(maxsiz[u], sz - siz[u]);
    if(maxsiz[u] < maxsiz[rt])
    {
        rt = u;
    }
}

int dd[N], tt;
void calc_dist(int u, int fa)
{
    dd[++ tt] = dist[u];
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == fa || vis[j]) continue;
        dist[j] = dist[u] + w[i];
        calc_dist(j, u);
    }
}

queue<int> tag;
void dfz(int x, int fa)
{
    tf[0] = true;
    tag.push(0);
    vis[x] = true;
    for(int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == fa || vis[j]) continue;
        dist[j] = w[i];
        calc_dist(j, x);
        for(int k = 1; k <= tt; k ++ )
            for(int u = 1; u <= m; u ++ )
                if(q[u] >= dd[k]) res[u] |= tf[q[u] - dd[k]];
        for(int k = 1; k <= tt; k ++ )
            if(dd[k] < 10000000)
            {
                tf[dd[k]] = true;
                tag.push(dd[k]);
            }
        tt = 0;
    }
    while(!tag.empty()) tf[tag.front()] = false, tag.pop();
    for(int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == fa || vis[j]) continue;
        rt = 0;
        maxsiz[rt] = INF;
        calc_siz(j, x, siz[j]);
        calc_siz(rt, -1, siz[j]);
        dfz(rt, x);
    }
}

int main()
{
    memset(h, -1, sizeof h);

    n = read(), m = read();
    for(int i = 1; i < n; i ++ )
    {
        int a = read(), b = read(), c = read();
        add(a, b, c), add(b, a, c);
    }

    for(int i = 1; i <= m; i ++ )
        q[i] = read();

    rt = 0;
    maxsiz[rt] = INF;
    siz[1] = n;
    calc_siz(1, -1, n);
    calc_siz(rt, -1, n);
    dfz(rt, -1);
    for(int i = 1; i <= m; i ++ )
        if(res[i])
            puts("AYE");
        else puts("NAY");
    
    return 0;
}

P4178 Tree

本题和上面差不多，只是多了查询点对的数量，因此用平衡树维护即可。

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
172
173
174
175
176
177
178
179
180
181

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int h[N], e[N], ne[N], w[N], idx;
int maxsiz[N], siz[N], dist[N];
bool vis[N];
int rt;
int n, k;

struct fhq
{
    struct node
    {
        int l, r;
        int val, key;
        int siz;
    }t[N];
    int root, cnt;

    inline int New(int val)
    {
        t[++ cnt].val = val;
        t[cnt].key = rand();
        t[cnt].siz = 1;
        t[cnt].l = t[cnt].r = 0;
        return cnt;
    }

    inline void pushup(int p)
    {
        t[p].siz = t[t[p].l].siz + t[t[p].r].siz + 1;
    }

    int merge(int x, int y)
    {
        if(!x || !y) return x + y;
        if(t[x].key > t[y].key)
        {
            t[x].r = merge(t[x].r, y);
            pushup(x);
            return x;
        }
        else
        {
            t[y].l = merge(x, t[y].l);
            pushup(y);
            return y;
        }
    }

    void split(int p, int val, int &x, int &y)
    {
        if(!p) x = y = 0;
        else
        {
            if(t[p].val <= val)
            {
                x = p;
                split(t[p].r, val, t[x].r, y);
            }
            else
            {
                y = p;
                split(t[p].l, val, x, t[y].l);
            }
            pushup(p);
        } 
    }

    int x, y, z;
    inline void insert(int val)
    {
        split(root, val, x, y);
        root = merge(merge(x, New(val)), y);
    }

    inline void clear()
    {
        cnt = root = 0;
    }

    inline int lowernums(int val)
    {
        split(root, val, x, y);
        int res = t[x].siz;
        root = merge(x, y);
        return res;
    }
} t;

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

void calc_siz(int u, int fa, int sz)
{
    siz[u] = 1;
    maxsiz[u] = 0;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == fa || vis[j]) continue;
        calc_siz(j, u, sz);
        siz[u] += siz[j];
        maxsiz[u] = max(maxsiz[u], siz[j]);
    }
    maxsiz[u] = max(maxsiz[u], sz - siz[u]);
    if(maxsiz[u] < maxsiz[rt])
    {
        rt = u;
    }
}

int dd[N], tt;
void calc_dis(int x, int fa)
{
    dd[++ tt] = dist[x];
    for(int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == fa || vis[j]) continue;
        dist[j] = dist[x] + w[i];
        calc_dis(j, x);
    }
}

ll ans;
void dfz(int u, int fa)
{
    vis[u] = true;
    t.insert(0);
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == fa || vis[j]) continue;
        dist[j] = w[i];
        calc_dis(j, u);
        for(int i = 1; i <= tt; i ++ )
            ans += t.lowernums(k - dd[i]);
        for(int i = 1; i <= tt; i ++ )
            t.insert(dd[i]);
        tt = 0;
    }
    t.clear();
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == fa || vis[j]) continue;
        rt = 0;
        maxsiz[rt] = INF;
        calc_siz(j, u, siz[j]);
        calc_siz(rt, -1, siz[j]);
        dfz(rt, u);
    }
}

int main()
{
    memset(h, -1, sizeof h);

    n = read();
    for(int i = 1; i < n; i ++ )
    {
        int a = read(), b = read(), c = read();
        add(a, b, c), add(b, a, c);
    }

    k = read();
    rt = 0;
    maxsiz[rt] = INF;
    calc_siz(1, -1, n);
    calc_siz(rt, -1, n);
    dfz(rt, -1);

    cout << ans << endl;
    
    return 0;
}

后记

其实点分治我还没有完全搞明白，现在做题也是大部分都是一头雾水，也因此只放了 2 道例题（能力有限），而且点分树什么的也没学，所以只能等以后再补充。