树分治学习笔记

好久都没写学习笔记了。

吐槽：代码太长，洛谷国际站又爆炸了，没法用云剪贴板。

引入

我们先来看看序列分治。序列分治通常是把一个大问题分成许多个小问题，最后合并就成了总的问题的答案。而树分治也是如此。

这里主要讲点分治和点分树，边分治不讲。~~因为不会~~

例题

P3806 【模板】点分治 1↗

点分治通常用于处理路径问题。比如这道题里的“有没有距离为 $k$ 的点对”其实就是“有没有长度为 $k$ 的路径”。

我们先将询问离线，随便认定一个点为根。那么路径有 $2$ 种：经过根的和不经过根的。不经过根的可以递归的处理子树进行分治。我们只考虑经过根的路径。我们可以进行一次 dfs，处理子树内每个点到根节点的距离，和它属于哪个子树。然后按照距离给每个点排序，循环每一个询问 $qry_i$ ，双指针找出没有长度为 $qry_i$ 且不属于同一个子树的点对。有就把 $ans_i$ 置为 $1$ 并 break。没有就继续。

这样我们就成功的搞出了一个看似天衣无缝的做法。但是我们发现，当树变成链的时候，这个算法会退化到 $O(n^2)$ 。究其原因是处理每个点所在的子树的时候，子树大小都是 $O(n)$ 的。而总共有 $n$ 个点，那么和起来就是 $O(n^2)$ 。

我们回到序列分治来找优化方法。我们发现，序列分治的分治中心一般是区间中点，因为满足这个性质：分出来的最大块最小，也就是最平均。因为分治的时间复杂度是 $\text{层数} \times O(n)$ 的。这样能使层数最小，从而使得时间复杂度最小。我们希望我们的点分治也能够这个样子。

我们发现，如果要使分的块（子树）最平均，我们想到重心当分治中心。每次找到重心作为根，这样就最平均了。那有人要问了：子树的重心不是当前节点的儿子的怎么办？因为我们会递归处理每个子树，当前块内的每条路径都会在当前或者递归后被处理。我们就把每次分治的中心设为重心，最大递归层数 $\log_2 n$ 。总时间复杂度 $O(n\log_2 n)$ 。

code:

1
#include<bits/extc++.h>
2
#define inf 0x3f3f3f3f
3
using namespace std;
4
const int maxn = 1e4 + 5;
5
int n,m;
6
int qry[105];
7
int head[maxn],idx;
8
bool vis[maxn],ans[105];
9
int dis[maxn],bel[maxn];
10
int siz[maxn],wei[maxn],ssiz,rt;
11
struct edge{int v,w,nxt;}e[maxn << 1];
12
bool cmp(int x,int y){return dis[x] < dis[y];}
13
void adde(int u,int v,int w)
14
{
15
    e[++idx] = edge{v,w,head[u]};
16
    head[u] = idx;
17
}
18
void dfs1(int u,int fa)
19
{//找重心
20
    siz[u] = 1,wei[u] = 0;
21
    for (int i = head[u]; i; i = e[i].nxt)
22
    {
23
        int v = e[i].v;
24
        if (v == fa || vis[v])
25
            continue;
26
        dfs1(v,u);
27
        siz[u] += siz[v];
28
        wei[u] = max(wei[u],siz[v]);
29
    }
30
    wei[u] = max(wei[u],ssiz - siz[u]);//还有根到u的那一段
31
    if (wei[u] < wei[rt])
32
        rt = u;
33
}
34
void dfs2(vector<int>&a,int u,int dist,int fa,int root)
35
{//找出子树内的点和它们所属的子树和离根节点的距离
36
    a.push_back(u);
37
    dis[u] = dist,bel[u] = root;
38
    for (int i = head[u]; i; i = e[i].nxt)
39
    {
40
        int v = e[i].v;
41
        if (v != fa && !vis[v])
42
            dfs2(a,v,dist + e[i].w,u,root);
43
    }
44
}
45
void calc(int u)//计算
46
{
47
    vector<int>a = {u};
48
    dis[u] = 0,bel[u] = u;
49
    for (int i = head[u]; i; i = e[i].nxt)
50
    {
51
        int v = e[i].v;
52
        if (!vis[v])
53
            dfs2(a,v,e[i].w,0,v);
54
    }
55
    sort(a.begin(),a.end(),cmp);
56
    for (int i = 1; i <= m; i++)
57
    {
58
        auto l = a.begin(),r = a.end() - 1;
59
        while (l != r && !ans[i])
60
        {
61
            if (dis[*l] + dis[*r] > qry[i])
62
                r--;
63
            else if (dis[*l] + dis[*r] < qry[i])
64
                l++;
65
            else if (bel[*l] == bel[*r])
66
            {
67
                if (dis[*r] == dis[*(r - 1)])
68
                    r--;
69
                else
70
                    l++;
71
            }
72
            else
73
                ans[i] = 1;
74
        }
75
    }
76
}
77
void dfs(int u)//分治
78
{
79
    vis[u] = 1;
80
    calc(u);
81
    for (int i = head[u]; i; i = e[i].nxt)
82
    {
83
        int v = e[i].v;
84
        if (vis[v])
85
            continue;
86
        wei[rt = 0] = inf;
87
        ssiz = siz[v];
88
        dfs1(v,0);
89
        dfs(rt);//以重心为根进行分治
90
    }
91
}
92
signed main()
93
{
94
    scanf("%d%d",&n,&m);
95
    for (int i = 1,u,v,w; i < n; i++)
96
    {
97
        scanf("%d%d%d",&u,&v,&w);
98
        adde(u,v,w);
99
        adde(v,u,w);
100
    }
101
    for (int i = 1; i <= m; i++)
102
    {
103
        scanf("%d",qry + i);
104
        if (!qry[i])//这里要特判 qry[i] = 0 的情况。
105
            ans[i] = 1;
106
    }
107
    wei[rt = 0] = inf;
108
    dfs1(1,0);
109
    dfs(rt);
110
    for (int i = 1; i <= m; i++)
111
        puts(ans[i] ? "AYE" : "NAY");
112
    return 0;
113
}

P5563 [Celeste-B] No More Running↗

题意：给定一颗树，对于每个点 $u$ 求以 $u$ 为端点的路径长度在模 $mod$ 意义下的最大值是多少。

看到树上的路径问题，我们马上就想到了点分治。设当前的根是 $rt$ ，设 $dis(u,v)$ 表示 $u,v$ 之间的距离模 $mod$ 。把当前分治区域内每个点 $u$ 到 $rt$ 的距离统计出来。然后在统计答案的时候，我们发现，我们统计的每个距离都不会超过 $mod$ ，这样子，两条路径加起来最多只会超过 $mod$ 一次。那么我们将超过 $mod$ 和不超过 $mod$ 分开讨论。把当前分治区域内每个点 $u$ 到 $rt$ 的距离都插入一个 multiset 中，统计答案时，对于不超过 $mod$ 的情况，在 multiset 里二分找到最后一个小于 $mod - dis_u$ 的元素；对于超过的，直接取最大的就行。

code:

1
#include<bits/extc++.h>
2
#define int long long
3
#define max(x,y) ((x) > (y) ? (x) : (y))
4
#define min(x,y) ((x) < (y) ? (x) : (y))
5
#define inf 0x3f3f3f3f3f3f3f3f
6
const int maxn = 1e5 + 5;
7
int n,mod;
8
bool vis[maxn];
9
int head[maxn],idx;
10
int dis[maxn],ans[maxn];
11
int siz[maxn],wei[maxn],rt,ssiz;
12
std::multiset<int>st;
13
struct edge{int v,w,nxt;}e[maxn << 1];
14
void adde(int u,int v,int w)
15
{
16
    e[++idx] = edge{v,w,head[u]};
17
    head[u] = idx;
18
}
19
void dfs1(int u,int fa)
20
{
21
    siz[u] = 1,wei[u] = 0;
22
    for (int i = head[u]; i; i = e[i].nxt)
23
    {
24
        int v = e[i].v;
25
        if (v == fa || vis[v])
26
            continue;
27
        dfs1(v,u);
28
        siz[u] += siz[v];
29
        wei[u] = max(wei[u],siz[v]);
30
    }
31
    wei[u] = max(wei[u],ssiz - siz[u]);
32
    if (wei[u] < wei[rt])
33
        rt = u;
34
}
35
void dfs2(int u,int fa)
36
{
37
    st.insert(dis[u]);
38
    for (int i = head[u]; i; i = e[i].nxt)
39
    {
40
        int v = e[i].v,w = e[i].w;
41
        if (v == fa || vis[v])
42
            continue;
43
        dis[v] = (dis[u] + w) % mod;
44
        dfs2(v,u);
45
    }
46
}
47
void set(int u,int fa,bool op)
48
{
49
    if (op)
50
        st.insert(dis[u]);
51
    else
52
        st.erase(st.find(dis[u]));
53
    for (int i = head[u]; i; i = e[i].nxt)
54
        if (int v = e[i].v; v != fa && !vis[v])
55
            set(v,u,op);
56
}
57
void dfs3(int u,int fa)
58
{
59
    ans[u] = max(ans[u],max(*(--st.lower_bound(mod - dis[u])) + dis[u],(dis[u] + *st.rbegin()) % mod));
60
    //这里就是在分讨两种情况。
61
    for (int i = head[u]; i; i = e[i].nxt)
62
        if (int v = e[i].v; v != fa && !vis[v])
63
            dfs3(v,u);
64
}
65
void dfs(int u)
66
{
67
    vis[u] = 1,dis[u] = 0;
68
    dfs2(u,0);
69
    ans[u] = max(ans[u],*st.rbegin());
70
    for (int i = head[u]; i; i = e[i].nxt)
71
    {
72
        int v = e[i].v;
73
        if (vis[v])
74
            continue;
75
        //保证两个点一定不在同一个子树内
76
        set(v,u,0);//擦除 multiset 里的当前子树的点
77
        dfs3(v,u);
78
        set(v,u,1);//插入回去
79
    }
80
    st.clear();
81
    for (int i = head[u]; i; i = e[i].nxt)
82
    {
83
        int v = e[i].v;
84
        if (vis[v])
85
            continue;
86
        wei[rt = 0] = inf;
87
        ssiz = siz[v];
88
        dfs1(v,u);
89
        dfs(rt);
90
    }
91
}
92
signed main()
93
{
94
    scanf("%lld%lld",&n,&mod);
95
    for (int i = 1,u,v,w; i < n; i++)
96
    {
97
        scanf("%lld%lld%lld",&u,&v,&w);
98
        adde(u,v,w);
99
        adde(v,u,w);
100
    }
101
    wei[rt = 0] = inf;
102
    ssiz = n;
103
    dfs1(1,0);
104
    dfs(rt);
105
    for (int i = 1; i <= n; i++)
106
        printf("%lld\n",ans[i]);
107
    return 0;
108
}

UVA12161 铁人比赛 Ironman Race in Treeland↗

题意：有一颗树，树上的每条边有两个权值：长度和代价。一条路径的总代价是这条路径上的边的代价之和。求代价不超过 $m$ 的最长路径长度。

我们看到：不超过 $m$ ，想到用一个单调的数据结构来维护。对于一条代价为 $damage$ 的路径，考虑在数据结构上二分出小于 $m - damage$ 的最大的长度。既然如此，有结论：当 $D_i \le D_j$ 且 $L_i \ge L_j$ ，肯定有 $i$ 比 $j$ 优， $j$ 就完蛋了。于是我们得维护一个 $D$ 和 $L$ 都单调的数据结构。std::map 是一个不错的选择。

code:

1
#include<bits/extc++.h>
2
#define int long long
3
#define inf 0x3f3f3f3f3f3f3f3f
4
using namespace std;
5
typedef pair<int,int> pii;
6
const int maxn = 2e5 + 5;
7
int n,k,ans;
8
bool vis[maxn];
9
int head[maxn],idx;
10
int siz[maxn],wei[maxn],ssiz,rt;
11
vector<pii>a;
12
map<int,int>mp;
13
struct edge{int v,d,w,nxt;}e[maxn << 1];
14
void read(int &x)
15
{
16
    x = 0; int f = 1;
17
    char ch = getchar();
18
    while (!isdigit(ch)){f = ch == '-' ? -1 : 1; ch = getchar();}
19
    while (isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
20
    x *= f;
21
}
22
void adde(int u,int v,int d,int w)
23
{
24
    e[++idx] = edge{v,d,w,head[u]};
25
    head[u] = idx;
26
}
27
void dfs1(int u,int fa)
28
{
29
    siz[u] = 1,wei[u] = 0;
30
    for (int i = head[u]; i; i = e[i].nxt)
31
    {
32
        int v = e[i].v;
33
        if (v == fa || vis[v])
34
            continue;
35
        dfs1(v,u);
36
        siz[u] += siz[v];
37
        wei[u] = max(wei[u],siz[v]);
38
    }
39
    wei[u] = max(wei[u],ssiz - siz[u]);
40
    if (wei[u] < wei[rt])
41
        rt = u;
42
}
43
void dfs2(int u,pii dis,int fa)
44
{
45
    a.push_back(dis);//把每个点到当前根的距离统计出来
46
    for (int i = head[u]; i; i = e[i].nxt)
47
    {
48
        int v = e[i].v,d = e[i].d,w = e[i].w;
49
        if (v == fa || vis[v])
50
            continue;
51
        dfs2(v,{dis.first + d,dis.second + w},u);
52
    }
53
}
54
void upd(int x,int y)
55
{
56
    auto p = mp.upper_bound(x);
57
    if (p == mp.begin() || (--p)->second < y)
58
    {
59
        mp[x] = y;
60
        p = mp.upper_bound(x);
61
        while (p != mp.end() && p->second <= y)
62
            mp.erase(p++);//对于那些不优的扔出去
63
    }
64
}
65
void calc(int u)
66
{
67
    mp.clear();
68
    mp[0] = 0;
69
    for (int i = head[u]; i; i = e[i].nxt)
70
    {
71
        int v = e[i].v;
72
        if (vis[v])
73
            continue;
74
        a.clear();
75
        dfs2(v,{e[i].d,e[i].w},u);
76
        for (auto &[d,w] : a)
77
        {
78
            auto p = mp.upper_bound(k - d);//二分到最长的代价小于 k - d 的路径
79
            if (p != mp.begin())
80
                ans = max(ans,w + (--p)->second);
81
        }
82
        for (auto &[d,w] : a)
83
            upd(d,w);
84
    }
85
}
86
void dfs(int u)
87
{
88
    vis[u] = 1;
89
    calc(u);
90
    for (int i = head[u]; i; i = e[i].nxt)
91
    {
92
        int v = e[i].v;
93
        if (vis[v])
94
            continue;
95
        wei[rt = 0] = inf;
96
        ssiz = siz[v];
97
        dfs1(v,u);
98
        dfs(rt);
99
    }
100
}
101
void solve()
102
{
103
    read(n),read(k);
104
    fill(vis + 1,vis + n + 1,0);
105
    fill(head + 1,head + n + 1,0);
106
    ans = idx = 0;
107
    for (int i = 1,u,v,w,d; i < n; i++)
108
    {
109
        read(u),read(v),read(d),read(w);
110
        adde(u,v,d,w);
111
        adde(v,u,d,w);
112
    }
113
    wei[rt = 0] = inf;
114
    ssiz = n;
115
    dfs1(1,0);
116
    dfs(rt);
117
}
118
signed main()
119
{
120
    int t;
121
    read(t);
122
    for (int i = 1; i <= t; i++)
123
    {
124
        solve();
125
        printf("Case %lld: %lld\n",i,ans);
126
    }
127
    return 0;
128
}

P6329 【模板】点分树 | 震波↗

看到题目，首先就想到对于每个查询都跑一边点分治。但是这样下来，时间肯定吃不消。这时候，我们就要引入点分树。

先来讲讲点分树是啥。我们先掏一颗树：

那么点分树就是当前分治中心到下一层分治中心连边，就像这样：

很显然和原树并没有什么关系。父子关系变得乱糟糟的。

但是，我们发现，点分树的树高只有 $\log_2 n$ ，简直就是暴力福音。还有，点分树上的 $\operatorname{lca}(u,v)$ 一定在原树 $u \to v$ 的路径上。我们可以通过把原树上 $u \to v$ 的路径在点分树上 $\operatorname{lca}(u,v)$ 这个点这里分开来处理路径问题。

回到这题。我们考虑枚举 $x,u$ 在点分树上的 lca $v$ ，那么我们要找的答案就是：

ans = \sum\limits_{dis(x,v) + dis(v,u) \le k}a_u = \sum\limits_{dis(v,u) \le k - dis(x,v)}a_u

让我们想想有什么 $u$ 会有 $\operatorname{lca}(u,x) = v$ ，明显是 $v$ 的整个子树扣掉 $x$ 所在的子树。对于每个点 $x$ 建树状数组，下标为 $i$ 的位置维护 $\sum\limits_{dis(x,v) = i}$ 。每次查询一个区间和就行。这样我们就搞定了一个路径。

但是一整条路径是要两条路径拼起来的啊，剩下的那条路径来自被扣掉的 $x$ 所在的子树。再对每个点都开一个树状数组。下标为 $i$ 的位置维护 $\sum\limits_{dis(u,fa_x) = i}a_u$ ，其中 $u$ 在 $x$ 子树内。每次查询 $[0,k - dis(x,v)]$ 的区间和就行了。

code:

1
#include<bits/extc++.h>
2
#define int long long
3
#define inf 0x3f3f3f3f3f3f3f3f
4
#define lowbit(x) ((x) & (-x))
5
using namespace std;
6
const int maxn = 1e5 + 5;
7
int n,m,a[maxn];
8
vector<int>g[maxn];
9
vector<int>tree[maxn][2];
10
void resize(int id,int siz){tree[id][0].resize(siz),tree[id][1].resize(siz);}
11
void upd(int i,int id,int op,int val)
12
{
13
    for (i++; i < tree[id][op].size(); i += lowbit(i))
14
        tree[id][op][i] += val;
15
}
16
int que(int i,int id,int op)
17
{
18
    int ret = 0;
19
    i = min(i + 1,(int)tree[id][op].size() - 1);
20
    for (; i; i -= lowbit(i))
21
        ret += tree[id][op][i];
22
    return ret;
23
}
24
namespace ctr
25
{
26
    int siz[maxn],son[maxn],dep[maxn],top[maxn],fa[maxn];
27
    void dfs1(int u,int pre)
28
    {
29
        fa[u] = pre,dep[u] = dep[pre] + 1,siz[u] = 1;
30
        for (auto v : g[u])
31
        {
32
            if (v == pre)
33
                continue;
34
            dfs1(v,u);
35
            siz[u] += siz[v];
36
            if (siz[v] > siz[son[u]])
37
                son[u] = v;
38
        }
39
    }
40
    void dfs2(int u,int tp)
41
    {
42
        top[u] = tp;
43
        if (!son[u])
44
            return ;
45
        dfs2(son[u],tp);
46
        for (auto v : g[u])
47
            if (v != fa[u] && v != son[u])
48
                dfs2(v,v);
49
    }
50
    int lca(int u,int v)
51
    {
52
        while (top[u] != top[v])
53
        {
54
            if (dep[top[u]] < dep[top[v]])
55
                swap(u,v);
56
            u = fa[top[u]];
57
        }
58
        return dep[u] < dep[v] ? u : v;
59
    }
60
    int dis(int u,int v){return dep[u] + dep[v] - (dep[lca(u,v)] << 1);}
61
}
62
namespace algo
63
{
64
    bool vis[maxn];
65
    int ssiz,_min,rt;
66
    int siz[maxn],fa[maxn];
67
    int dfs1(int u,int fa)
68
    {
69
        int ret = 1;
70
        for (auto v : g[u])
71
            if (v != fa && !vis[v])
72
                ret += dfs1(v,u);
73
        return ret;
74
    }
75
    void dfs2(int u,int fa)
76
    {
77
        // cerr << "114514\n";
78
        siz[u] = 1;
79
        int _max = 0;
80
        for (auto v : g[u])
81
        {
82
            if (v == fa || vis[v])
83
                continue;
84
            dfs2(v,u);
85
            siz[u] += siz[v];
86
            _max = max(_max,siz[v]);
87
        }
88
        _max = max(_max,ssiz - siz[u]);
89
        if (_max < _min)
90
        {
91
            _min = _max;
92
            rt = u;
93
        }
94
    }
95
    void dfs(int u)
96
    {
97
        resize(u,dfs1(u,0) + 2);
98
        vis[u] = 1;
99
        for (auto v : g[u])
100
        {
101
            if (vis[v])
102
                continue;
103
            _min = inf,rt = 0;
104
            ssiz = dfs1(v,0);
105
            dfs2(v,0);
106
            fa[rt] = u;
107
            dfs(rt);
108
        }
109
    }
110
}
111
void upd(int u,int val)
112
{
113
    for (int i = u; i; i = algo::fa[i])
114
        upd(ctr::dis(i,u),i,0,val);
115
    for (int i = u; algo::fa[i]; i = algo::fa[i])
116
        upd(ctr::dis(algo::fa[i],u),i,1,val);
117
}
118
int que(int u,int k)
119
{
120
    int ret = que(k,u,0);
121
    for (int i = u; algo::fa[i]; i = algo::fa[i])
122
    {
123
        int dis = ctr::dis(algo::fa[i],u);
124
        if (dis > k)
125
            continue;
126
        ret += que(k - dis,algo::fa[i],0) - que(k - dis,i,1);
127
    }
128
    return ret;
129
}
130
signed main()
131
{
132
    // freopen("P6329_1.in","r",stdin);
133
    // freopen("out2.txt","w",stdout);
134
    scanf("%lld%lld",&n,&m);
135
    for (int i = 1; i <= n; i++)
136
        scanf("%lld",a + i);
137
    for (int i = 1,u,v; i < n; i++)
138
    {
139
        scanf("%lld%lld",&u,&v);
140
        g[u].push_back(v),g[v].push_back(u);
141
    }
142
    ctr::dfs1(1,0),ctr::dfs2(1,1);
143
    algo::_min = inf;
144
    algo::rt = 0;
145
    algo::ssiz = n;
146
    algo::dfs2(1,0);
147
    algo::dfs(algo::rt);
148
    for (int i = 1; i <= n; i++)
149
        upd(i,a[i]);
150
    int ans = 0,op,x,y;
151
    while (m--)
152
    {
153
        scanf("%lld%lld%lld",&op,&x,&y);
154
        x ^= ans,y ^= ans;
155
        if (op == 0)
156
        {
157
            ans = que(x,y);
158
            printf("%lld\n",ans);
159
        }
160
        else
161
        {
162
            upd(x,y - a[x]);
163
            a[x] = y;
164
        }
165
    }
166
    return 0;
167
}

Thanks for reading!