1. 首页
  2. 文章中心
  3. 数据结构

树链剖分_笔记：数据结构-数链剖分 (yuque.com)树上LCA2(代码源#534）ZJOI2008, 树的统计(代码源#819）SDOI2011, 染色(代码源#820）

157 阅读 0 评论
我是靠谱客的博主 拉长蓝天，这篇文章主要介绍树链剖分_笔记：数据结构-数链剖分 (yuque.com)树上LCA2(代码源#534）ZJOI2008, 树的统计(代码源#819）SDOI2011, 染色(代码源#820），现在分享给大家，希望可以做个参考。

目录

笔记：数据结构-数链剖分 (yuque.com)

树上LCA2(代码源#534）

代码

ZJOI2008, 树的统计(代码源#819）

代码

SDOI2011, 染色(代码源#820）

代码 

笔记：数据结构-数链剖分 (yuque.com)

树上LCA2(代码源#534）

树上LCA2 - 题目 - Daimayuan Online Judge

给你一棵树，树以下列方式给出：

树以下列方式给出：

  • 编号为 11 的节点为根；

  • 输入第一行给出一个数 nn，表示一共有 nn 个节点；

  • 接下来 n−1n−1 行，每行给出两个数 x,y(x≠y)x,y(x≠y)，表示 x,yx,y 之间有一条边。

接下来有 mm 组询问，每组询问有两个数 x,y(x≠y)x,y(x≠y), 你需要求出 x,yx,y 的最近公共祖先。

输入格式

见题面。

输出格式

输出共 mm 行，每行 11 个数表示每次询问答案。

样例输入

复制代码
1
2
3
4
5
6
7
4
1 2
1 3
3 4
2
1 2
2 4

样例输出

复制代码
1
2
1
1

数据规模

对于所有数据，保证1≤n,m≤100000,1≤x,y≤n,x≠y。

时间复杂度：O(n)-O(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
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 101000;

int n, m;
vector<int>e[N];//边
int sz[N], hs[N], top[N], dep[N], fa[N];

//第一遍DFS->子树大小，重儿子，父亲，深度
void dfs1(int u, int f) {//结点，父节点
	sz[u] = 1;//子树节点数
	hs[u] = -1;//重儿子
	fa[u] = f;//父节点
	dep[u] = dep[f] + 1;//深度
	for (auto v : e[u]) {//遍历与u相连的每个子节点
		if (v == f)continue;
		dfs1(v, u);
		sz[u] += sz[v];//加上此子节点为根的子树节点数
		if (hs[u] == -1 || sz[v] > sz[hs[u]])//更新重儿子节点序号
			hs[u] = v;
	}
}

//第二遍DFS->重链上的链头的元素
void dfs2(int u, int t) {
	top[u] = t;//链头的节点序号
	if (hs[u] != -1) {
		dfs2(hs[u], t);
	}for (auto v : e[u]) {
		if (v != fa[u] && v != hs[u])//找轻儿子
			dfs2(v, v);//轻儿子的头节点就是自己
	}
}

int LCA(int u, int v) {
	while (top[u] != top[v]) {
		if (dep[top[u]] < dep[top[v]])v = fa[top[v]];
		else u = fa[top[u]];
	}if (dep[u] < dep[v])return u;
	else return v;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		e[u].push_back(v);
		e[v].push_back(u);
	}dfs1(1, 0);
	dfs2(1, 1);
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		printf("%dn", LCA(u, v));
	}
  	return 0;
}

ZJOI2008, 树的统计(代码源#819）

ZJOI2008, 树的统计 - 题目 - Daimayuan Online Judge

一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作：

  1. CHANGE u t，把结点uu的权值改为t。
  2. QMAX u v，询问从点u到点v的路径上的节点的最大权值
  3. QSUM u v， 询问从点u到点v的路径上的节点的权值和。注意：从点u到点v的路径上的节点包括u和v本身。

输入格式

输入的第一行为一个整数n，表示节点的个数。接下来n–1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。

接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。接下来一行，为一个整数q，表示操作的总数。

接下来q行，每行一个操作，以CHANGE u t或者QMAX u v或者QSUM u v的形式给出。

保证1≤n≤3×10^4,0≤q≤2×10^4,1≤n≤3×10^4,0≤q≤2×10^4，中途操作中保证每个节点的权值w在−3×10^4到3×10^4之间。

输出格式

对于每个QMAX或者QSUM的操作，每行输出一个整数表示要求输出的结果。

样例输入

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

样例输出

复制代码
1
2
3
4
5
6
7
8
9
10
4
1
2
2
10
6
5
6
5
16

代码

复制代码
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 101000;
#define mid (l+r)/2

int n, m, a[N];
vector<int>e[N];
int l[N], r[N], idx[N];
int sz[N], hs[N], tot, top[N], dep[N], fa[N];

struct info {
	int maxv, sum;
};

info operator+(const info& l, const info& r) {
    info temp = { max(l.maxv, r.maxv), l.sum + r.sum };
    return temp;
}

struct node {
	info val;
}seg[N * 4];

void update(int id) {
	seg[id].val = seg[id * 2].val + seg[id * 2 + 1].val;
}

void build(int id, int l, int r) {
	if (l == r) {
		//l号点，DFS序中第l个点
        info  temp = { a[idx[l]],a[idx[l]] };
        //cout << id<<' '<<l << endl;
		seg[id].val = temp;
	}
	else {
		int mid ;
		build(id * 2, l, mid);
		build(id * 2 + 1, mid + 1, r);
		update(id);
	}
}

void change(int id, int l, int r, int pos, int val) {
	if (l == r) {
		seg[id].val = { val, val };
	}
	else {
		int mid;
		if (pos <= mid)change(id * 2, l, mid, pos, val);
		else change(id * 2 + 1, mid + 1, r, pos, val);
		update(id);
	}
}

info query(int id, int l, int r, int ql, int qr) {
	if (l == ql && r == qr)return seg[id].val;
	int mid;
	if (qr <= mid)return query(id * 2, l, mid, ql, qr);
	else if (ql > mid)return query(id * 2 + 1, mid + 1, r, ql, qr);
	else {
		return query(id * 2, l, mid, ql, mid) +
			query(id * 2 + 1, mid + 1, r, mid + 1, qr);
	}
}
//第一遍DFS 子树大小，重儿子，父亲，深度
void dfs1(int u, int f) {
	sz[u] = 1; 
	hs[u] = -1;
	fa[u] = f;
	dep[u] = dep[f] + 1;
	for (auto v : e[u]) {
		if (v == f)continue;
		dfs1(v, u);
		sz[u] += sz[v];
		if (hs[u] == -1 || sz[v] > sz[hs[u]])
			hs[u] = v;
	}
}
//第二遍DFS 每个点DFS序，重链上的链头的元素
void dfs2(int u, int t) {
	top[u] = t;
	l[u] = ++tot;
	idx[tot] = u;
	if (hs[u] != -1) {
		dfs2(hs[u], t);
	}for (auto v : e[u]) {
		if (v != fa[u] && v != hs[u]) {
			dfs2(v, v);
		}
	}r[u] = tot;
}

info query(int u, int v) {
	info ans{ (int)-1e9,0 };
	while (top[u] != top[v]) {
		if (dep[top[u]] < dep[top[v]]) {
			ans = ans + query(1, 1, n, l[top[v]], l[v]);
			v = fa[top[v]];
		}
		else {
			ans = ans + query(1, 1, n, l[top[u]], l[u]);
			u = fa[top[u]];
		}
	}if (dep[u] <= dep[v])ans = ans + query(1, 1, n, l[u], l[v]);
	else ans = ans + query(1, 1, n, l[v], l[u]);
	return ans;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		e[u].push_back(v);
		e[v].push_back(u);
	}for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    dfs1(1, 0); //cout << "end1" << endl;
    dfs2(1, 1); //cout << "end2" << endl;
	build(1, 1, n);
	scanf("%d", &m);
	for (int i = 1; i <= m; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		static char op[10];
      
		scanf("%s%d%d", op,&u, &v);
		if (op[0] == 'C') {
			change(1, 1, n, l[u], v);
		}
		else {
			info ans = query(u, v);
			if (op[1] == 'M')printf("%dn", ans.maxv);
			else printf("%dn", ans.sum);
		}
	}
	return 0;
}

SDOI2011, 染色(代码源#820）

SDOI2011, 染色 - 题目 - Daimayuan Online Judge

给定一棵 nn 个节点的无根树，共有 mm 个操作，操作分为两种：

  1. 将节点 aa 到节点 bb 的路径上的所有点（包括 aa 和 bb）都染成颜色 cc。

  2. 询问节点 aa 到节点 bb 的路径上的颜色段数量。

颜色段的定义是极长的连续相同颜色被认为是一段。例如 112221 由三段组成：11、222、1。

输入格式

输入的第一行是用空格隔开的两个整数，分别代表树的节点个数 nn 和操作个数 mm。

第二行有 nn 个用空格隔开的整数，第 ii 个整数 wiwi 代表结点 ii 的初始颜色。

接下来 n−1n−1 行，每行两个用空格隔开的整数 u,vu,v，代表树上存在一条连结节点 uu 和节点 vv 的边。

接下来mm行，每行描述一个操作，其格式为：

每行首先有一个字符 opop，代表本次操作的类型。

若 opop 为 C，则代表本次操作是一次染色操作，在一个空格后有三个用空格隔开的整数 a,b,ca,b,c，代表将 aa 到 bb 的路径上所有点都染成颜色 cc。

若 opop 为 Q，则代表本次操作是一次查询操作，在一个空格后有两个用空格隔开的整数 a,ba,b，表示查询 aa 到 bb 路径上的颜色段数量。

保证1≤n,m≤105,1≤wi,c≤1091≤n,m≤105,1≤wi,c≤109。

输出格式

对于每次查询操作，输出一行一个整数代表答案。

样例输入

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
6 5
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5

样例输出

复制代码
1
2
3
3
1
2

代码 

复制代码
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
185
#include <bits/stdc++.h>
using namespace std;
#define ls (now << 1)
#define rs (now << 1 | 1)
const int N = 1e5 + 9;

int n, q, w[N], wson[N], fa[N], dfn[N], siz[N], top[N], deep[N], tot, id[N];
vector<int> edg[N];

void dfs1(int u, int f, int d) {
    deep[u] = d;
    fa[u] = f;
    wson[u] = -1;
    siz[u] = 1;
    for (auto v : edg[u]) {
        if (v == f) continue;
        dfs1(v, u, d + 1);
        siz[u] += siz[v];
        if (wson[u] == -1 || siz[wson[u]] < siz[v]) {
            wson[u] = v;
        }
    }
}

void dfs2(int u, int f, int ace) {
    top[u] = ace;
    dfn[u] = ++tot;
    id[tot] = u;
    if (wson[u] != -1) {
        dfs2(wson[u], u, ace);
    }
    for (auto v : edg[u]) {
        if (v == f || v == wson[u]) continue;
        dfs2(v, u, v);
    }
}

struct info {
    int l, r, s;
};

struct node {
    info val;
    int tag;
} seg[N << 2];

info operator+(const info& l, const info& r) {
    info res;
    res.l = l.l;
    res.r = r.r;
    res.s = l.s + r.s - (l.r == r.l);
    return res;
}

void update(int now, int col) {
    seg[now].val = { col, col, 1 };
    seg[now].tag = col;
}

void pushdown(int now) {
    if (seg[now].tag != 0) {
        update(ls, seg[now].tag);
        update(rs, seg[now].tag);
        seg[now].tag = 0;
    }
}

void build(int now, int l, int r) {
    seg[now].tag = 0;
    if (l == r) {
        seg[now].val = { w[id[l]], w[id[l]], 1 };
        return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    seg[now].val = seg[ls].val + seg[rs].val;
}

void modify(int now, int l, int r, int ml, int mr, int col) {
    if (l >= ml && r <= mr) {
        update(now, col);
        return;
    }
    pushdown(now);
    int mid = (l + r) >> 1;
    if (ml <= mid) {
        modify(ls, l, mid, ml, mr, col);
    }
    if (mr > mid) {
        modify(rs, mid + 1, r, ml, mr, col);
    }
    seg[now].val = seg[ls].val + seg[rs].val;
}

info query(int now, int l, int r, int ml, int mr) {
    if (l == ml && r == mr) {
        return seg[now].val;
    }
    pushdown(now);
    int mid = (l + r) >> 1;
    info res;
    if (mr <= mid) {
        res = query(ls, l, mid, ml, mr);
    }
    else if (ml > mid) {
        res = query(rs, mid + 1, r, ml, mr);
    }
    else {
        res = query(ls, l, mid, ml, mid) + query(rs, mid + 1, r, mid + 1, mr);
    }
    seg[now].val = seg[ls].val + seg[rs].val;
    return res;
}

void modify_path(int x, int y, int col) {
    while (top[x] != top[y]) {
        if (deep[top[x]] > deep[top[y]]) {
            modify(1, 1, n, dfn[top[x]], dfn[x], col);
            x = fa[top[x]];
        }
        else {
            modify(1, 1, n, dfn[top[y]], dfn[y], col);
            y = fa[top[y]];
        }
    }
    if (deep[x] > deep[y]) {
        modify(1, 1, n, dfn[y], dfn[x], col);
    }
    else {
        modify(1, 1, n, dfn[x], dfn[y], col);
    }
}

int query_path(int x, int y) {
    info rx = { 0, 0, 0 }, ry = { 0, 0, 0 };
    while (top[x] != top[y]) {
        if (deep[top[x]] > deep[top[y]]) {
            rx = query(1, 1, n, dfn[top[x]], dfn[x]) + rx;
            x = fa[top[x]];
        }
        else {
            ry = query(1, 1, n, dfn[top[y]], dfn[y]) + ry;
            y = fa[top[y]];
        }
    }
    if (deep[x] > deep[y]) {
        rx = query(1, 1, n, dfn[y], dfn[x]) + rx;
    }
    else {
        ry = query(1, 1, n, dfn[x], dfn[y]) + ry;
    }
    return rx.s + ry.s - (rx.l == ry.l);
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
    }
    for (int i = 1; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        edg[x].push_back(y);
        edg[y].push_back(x);
    }
    dfs1(1, 0, 1);
    dfs2(1, 0, 1);
    build(1, 1, n);
    for (int i = 1; i <= q; i++) {
        char s[10];
        scanf("%s", s);
        if (s[0] == 'C') {
            int u, v, x;
            scanf("%d%d%d", &u, &v, &x);
            modify_path(u, v, x);
        }
        else {
            int u, v;
            scanf("%d%d", &u, &v);
            printf("%dn", query_path(u, v));
        }
    }
    return 0;
}

最后

以上就是拉长蓝天最近收集整理的关于树链剖分_笔记：数据结构-数链剖分 (yuque.com)树上LCA2(代码源#534）ZJOI2008, 树的统计(代码源#819）SDOI2011, 染色(代码源#820）的全部内容，更多相关树链剖分_笔记：数据结构-数链剖分内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(104)

相关文章

Dijstra最短路详解
Dijstra最短路详解
最短路径-Dijkstra(迪杰斯特拉)算法最短路径-Dijkstra(迪杰斯特拉)算法
最短路径-Dijkstra(迪杰斯特拉)算法最短路径-Dijkstra(迪杰斯特拉)算法
Dijkstra算法最短路径问题详解
Dijkstra算法最短路径问题详解
1088: 最短路（SPFA算法 &dij）
1088: 最短路（SPFA算法 &dij）
树链剖分_笔记：数据结构-数链剖分 (yuque.com)树上LCA2(代码源#534）ZJOI2008, 树的统计(代码源#819）SDOI2011, 染色(代码源#820）
树链剖分_笔记：数据结构-数链剖分 (yuque.com)树上LCA2(代码源#534）ZJOI2008, 树的统计(代码源#819）SDOI2011, 染色(代码源#820）
图结构练习——最短路径
图结构练习——最短路径
Dijkstra算法求无向带权图最短路径——Java
Dijkstra算法求无向带权图最短路径——Java
图的最短路径算法
图的最短路径算法

评论列表共有 0 条评论

立即
投稿
返回
顶部