树链剖分

ACM

2018年6月13日12:55:26突然更新


学习的博客
树链剖分
lct教程
lct2
lct3
lct集训队论文一篇

疑问

一个树形的结构，那么怎么根据深度的属性来来接左右的孩子？（感觉就是随机连接的？
是不是每一个节点只会记录一个儿子，而一个splay会有一个父亲节点，并且这个父亲节点会指向上面的树的节点？

lct模板

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 300005;
const int inf = 2e9;
int n,m,top;
int fa[maxn],c[maxn][2];
int val[maxn], mx[maxn], u[maxn], v[maxn];
int q[maxn];
bool rev[maxn];
int lz[maxn];
struct Edge{
    int to, next;
}edge[maxn<<2];
int tot, head[maxn];
void init(){
    tot = 0;
    memset(head, -1, sizeof(head));
    memset(lz, 0, sizeof(lz));
    memset(mx, 0, sizeof(mx));
    memset(rev, 0, sizeof(rev));
    memset(c, 0, sizeof(c));
    memset(fa, 0, sizeof(fa));
}
bool isroot(int x)
{
    return c[fa[x]][0]!=x && c[fa[x]][1]!=x;
}
void update(int x)
{
    int l=c[x][0], r=c[x][1];
    mx[x]=max(mx[l], max(mx[r], val[x]));
}
void pushdown(int x)
{
    int l=c[x][0],r=c[x][1];
    if(lz[x]){
        if(l) lz[l] += lz[x], mx[l] += lz[x], val[l] += lz[x];
        if(r) lz[r] += lz[x], mx[r] += lz[x], val[r] += lz[x];
        lz[x] = 0;
    }
    if(rev[x])
    {
        rev[x]^=1;rev[l]^=1;rev[r]^=1;
        swap(c[x][0],c[x][1]);
    }
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],l,r;
    l=(c[y][1]==x);r=l^1;
    if(!isroot(y))c[z][c[z][1]==y]=x;
    fa[c[x][r]]=y;fa[y]=x;fa[x]=z;
    c[y][l]=c[x][r];c[x][r]=y;
    update(y);update(x);
}
void splay(int x)
{
    top = 0;
    q[++top]=x;
    for(int i=x;!isroot(i);i=fa[i])
        q[++top]=fa[i];
    while(top)pushdown(q[top--]);
    while(!isroot(x))
    {
        int y=fa[x],z=fa[y];
        if(!isroot(y))
        {
            if(c[y][0]==x^c[z][0]==y)rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
}
void access(int x)
{
    for(int t=0;x;t=x,x=fa[x])
        splay(x),c[x][1]=t,update(x);
}
void makeroot(int x)
{
    access(x);splay(x);rev[x]^=1;
}
void link(int x,int y)
{
    makeroot(x);fa[x]=y;
}
void split(int x,int y)
{
    makeroot(x);access(y);splay(y);
}
void cut(int x,int y)
{
    split(x, y);
    //if(c[y][0]==x)c[y][0]=fa[x]=0;
    c[y][0]=fa[c[y][0]]=0;
    //pushup
    //update(y);
}
//为什么往左孩子找？
int find(int x){
    access(x);splay(x);
    //找到原来的根节点
    while(c[x][0])x=c[x][0];
    return x;
}

树链剖分题目推荐

1.【bzoj4034】[HAOI2015]T2
2.【bzoj2243】[SDOI2011]染色
3.【bzoj1984】月下“毛景树”
4.【bzoj3531】[Sdoi2014]旅行
5.【bzoj1036】[ZJOI2008]树的统计Count
6.【poj3237】Tree
7.Codeforces 343D Water Tree

hdu 4010 query on a tree

ac code

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
182
183
184
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 300005;
const int inf = 2e9;
int n,m,top;
int fa[maxn],c[maxn][2];
int val[maxn], mx[maxn], u[maxn], v[maxn];
int q[maxn];
bool rev[maxn];
int lz[maxn];
struct Edge{
    int to, next;
}edge[maxn<<2];
int tot, head[maxn];
void init(){
    tot = 0;
    memset(head, -1, sizeof(head));
    memset(lz, 0, sizeof(lz));
    memset(mx, 0, sizeof(mx));
    memset(rev, 0, sizeof(rev));
    memset(c, 0, sizeof(c));
    memset(fa, 0, sizeof(fa));
}
void add_edge(int u, int v){
    edge[tot].to = v, edge[tot].next = head[u], head[u] = tot++;
    edge[tot].to = u, edge[tot].next = head[v], head[v] = tot++;
}
bool isroot(int x)
{
    return c[fa[x]][0]!=x && c[fa[x]][1]!=x;
}
void update(int x)
{
    int l=c[x][0], r=c[x][1];
    mx[x]=max(mx[l], max(mx[r], val[x]));
}
void pushdown(int x)
{
    int l=c[x][0],r=c[x][1];
    if(lz[x]){
        if(l) lz[l] += lz[x], mx[l] += lz[x], val[l] += lz[x];
        if(r) lz[r] += lz[x], mx[r] += lz[x], val[r] += lz[x];
        lz[x] = 0;
    }
    if(rev[x])
    {
        rev[x]^=1;rev[l]^=1;rev[r]^=1;
        swap(c[x][0],c[x][1]);
    }
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],l,r;
    l=(c[y][1]==x);r=l^1;
    if(!isroot(y))c[z][c[z][1]==y]=x;
    fa[c[x][r]]=y;fa[y]=x;fa[x]=z;
    c[y][l]=c[x][r];c[x][r]=y;
    update(y);update(x);
}
void splay(int x)
{
    top = 0;
    q[++top]=x;
    for(int i=x;!isroot(i);i=fa[i])
        q[++top]=fa[i];
    while(top)pushdown(q[top--]);
    while(!isroot(x))
    {
        int y=fa[x],z=fa[y];
        if(!isroot(y))
        {
            if(c[y][0]==x^c[z][0]==y)rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
}
void access(int x)
{
    for(int t=0;x;t=x,x=fa[x])
        splay(x),c[x][1]=t,update(x);
}
void makeroot(int x)
{
    access(x);splay(x);rev[x]^=1;
}
void link(int x,int y)
{
    makeroot(x);fa[x]=y;
}
void split(int x,int y)
{
    makeroot(x);access(y);splay(y);
}
void cut(int x,int y)
{
    split(x, y);
    //if(c[y][0]==x)c[y][0]=fa[x]=0;
    c[y][0]=fa[c[y][0]]=0;
    //pushup
    //update(y);
}
//为什么往左孩子找？
int find(int x){
    access(x);splay(x);
    //找到原来的根节点
    while(c[x][0])x=c[x][0];
    return x;
}
void add(int w, int u, int v){
    split(u, v);
    val[v] += w, mx[v] += w, lz[v] += w;
}
int main()
{
    ios::sync_with_stdio(false);
    while(~scanf("%d", &n)){
        init();
        //mx[0]=-inf;
        int a, b;
        for(int i=1; i<n; i++){
            scanf("%d%d", &u[i], &v[i]);
            add_edge(u[i], v[i]);
        }
        for(int i=1; i<=n; i++) scanf("%d", &val[i]);
        for(int i=1; i<=n; i++) mx[i] = val[i];
        top = 0;
        q[++top]=1;
        //先xjb建好一棵树
        for(int k=1;k<=top;k++)
        {
            int now=q[k];
            for(int i=head[now];~i;i=edge[i].next)
                if(edge[i].to!=fa[now])
                {
                    fa[edge[i].to]=now;
                    q[++top]=edge[i].to;
                }
        }
        scanf("%d", &m);
        int op, w;
        while(m--){
            scanf("%d%d%d", &op, &a, &b);
            if(op == 1){
                if(find(a) == find(b)){
                    printf("-1\n");
                }
                else{
                    link(a, b);
                }
            }
            else if(op == 2){
                if(find(a)!=find(b)||a==b){
                    printf("-1\n");
                }
                else {
                    cut(a, b);
                }
            }
            else if(op == 3){
                scanf("%d", &w);
                if(find(b)!=find(w)){
                    printf("-1\n");
                }
                else add(a, b, w);
            }
            else{
                if(find(a)!=find(b)) printf("-1\n");
                else split(a, b), printf("%d\n", mx[b]);
            }
        }
        puts("");
    }
    return 0;
}

模板题

QTREE

ac code

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
struct Edge{
    int to, next;
}edge[maxn<<1];
int tot, head[maxn];
void add_edge(int u, int v){
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}
int pos;
int top[maxn];
int fa[maxn];
int deep[maxn];
int num[maxn];
int p[maxn];
int rp[maxn];
int son[maxn];
void init(){
    memset(head, -1, sizeof(head));
    tot = 0;
    pos = 0;
    memset(son, -1, sizeof(son));
}
void dfs1(int u, int pre, int d){
    deep[u] = d;
    fa[u] = pre;
    num[u] = 1;
    for(int i=head[u]; ~i; i = edge[i].next){
        int v = edge[i].to;
        if(v!=pre){
            dfs1(v, u, d+1);
            num[u] += num[v];
            if(son[u] == -1||num[v]>num[son[u]]){
                son[u] = v;
            }
        }
    }
}
void getpos(int u, int sp){
    top[u] = sp;
    p[u] = pos++;
    rp[p[u]] = u;
    if(son[u] == -1) return;
    getpos(son[u], sp);
    for(int i=head[u]; ~i; i = edge[i].next){
        int v = edge[i].to;
        if(v!=son[u]&&v!=fa[u]){
            getpos(v, v);
        }
    }
}
struct Node{
    int l, r;
    int Max;
}node[maxn<<2];
void build(int rt, int l, int r){
    node[rt].l = l;
    node[rt].r = r;
    node[rt].Max = 0;
    if(l == r) return;
    int mid = (l+r)/2;
    build(rt<<1, l, mid);
    build((rt<<1)|1, mid+1, r);
}
void push_up(int rt){
    node[rt].Max = max(node[rt<<1].Max, node[(rt<<1)|1].Max);
}
void update(int rt, int k, int val){
    if(node[rt].l == k&&node[rt].r == k){
        node[rt].Max = val;
        return;
    }
    int mid = (node[rt].l+node[rt].r)/2;
    if(k<=mid) update(rt<<1, k, val);
    else update((rt<<1)|1, k, val);
    push_up(rt);
}
int query(int rt, int l, int r){
    if(node[rt].l == l&&node[rt].r == r){
        return node[rt].Max;
    }
    int mid = (node[rt].l+node[rt].r)/2;
    if(r<=mid)return query(rt<<1, l, r);
    else if(l>mid) return query((rt<<1)|1, l, r);
    else return max(query(rt<<1, l, mid), query((rt<<1)|1, mid+1, r));
}
int find(int u, int v){
    int f1 = top[u], f2 = top[v];
    int temp = 0;
    while(f1!=f2){
        if(deep[f1]<deep[f2]){
            swap(f1, f2);
            swap(u, v);
        }
        temp = max(temp, query(1, p[f1], p[u]));
        u = fa[f1];
        f1 = top[u];
    }
    if(u == v) return temp;
    //u, v在同一根链上
    if(deep[u]>deep[v]) swap(u, v);
    return max(temp, query(1, p[son[u]], p[v]));
}
int e[maxn][3];
int main()
{
    ios::sync_with_stdio(false);
    int t, n;
    cin>>t;
    while(t--){
        init();
        cin>>n;
        for(int i=0; i<n-1; i++){
            cin>>e[i][0]>>e[i][1]>>e[i][2];
            add_edge(e[i][0], e[i][1]);
            add_edge(e[i][1], e[i][0]);
        }
        dfs1(1, 0, 0);
        getpos(1, 1);
        build(1, 0, pos-1);
        for(int i=0; i<n-1; i++){
            if(deep[e[i][0]]>deep[e[i][1]]){
                swap(e[i][0], e[i][1]);
            }
            update(1, p[e[i][1]], e[i][2]);//将更深的节点先更新
        }
        string op;
        int u, v;
        //cout<<op<<endl;
        while(cin>>op){
            if(op[0] == 'D') break;
            cin>>u>>v;
            if(op[0] == 'Q'){
                printf("%d\n", find(u, v));
            }
            else{
                update(1, p[e[u-1][1]], v);
            }
        }
    }
    return 0;
}
/*
1
3
1 2 1
2 3 2
QUERY 1 2
*/

未解决的问题

本文标题:树链剖分

文章作者:Babydragon

发布时间:2018-05-02, 21:29:28

最后更新:2018-08-17, 15:47:58

原始链接:http://baolintian.github.io/2018/05/02/树链剖分/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 疑问
    1. 1.1. lct模板
  2. 2. 树链剖分题目推荐
  3. 3. hdu 4010 query on a tree
    1. 3.1. ac code
  4. 4. 模板题
    1. 4.1. ac code
  5. 5. 未解决的问题
{{ live2d() }}