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

51 阅读 0 评论 34 点赞

我是靠谱客的博主拉长蓝天，最近开发中收集的这篇文章主要介绍树链剖分_笔记：数据结构-数链剖分 (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
1

数据规模

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

时间复杂度：O(n)-O(log n) //预处理-查询

代码

#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。我们将以下面的形式来要求你对这棵树完成一些操作：

CHANGE u t，把结点uu的权值改为t。
QMAX u v，询问从点u到点v的路径上的节点的最大权值
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的操作，每行输出一个整数表示要求输出的结果。

样例输入

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

样例输出

代码

#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 个操作，操作分为两种：

将节点 aa 到节点 bb 的路径上的所有点（包括 aa 和 bb）都染成颜色 cc。
询问节点 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。

输出格式

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

样例输入

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

样例输出

3
1
2

代码

#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）的全部内容，希望文章能够帮你解决树链剖分_笔记：数据结构-数链剖分 (yuque.com)树上LCA2(代码源#534）ZJOI2008, 树的统计(代码源#819）SDOI2011, 染色(代码源#820）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

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

本文分类：数据结构
浏览次数：51 次浏览
发布日期：2024-09-04 11:15:02
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_7_o_14_f2_13__23__10_1.html

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

概述

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

树上LCA2(代码源#534）

代码

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

输入格式

输出格式

样例输入

样例输出

代码

SDOI2011, 染色(代码源#820）

输入格式

输出格式

样例输入

样例输出

代码

最后

评论列表共有 0 条评论

发表评论取消回复

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

概述

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

树上LCA2(代码源#534）

代码

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

输入格式

输出格式

样例输入

样例输出

代码

SDOI2011, 染色(代码源#820）

输入格式

输出格式

样例输入

样例输出

代码

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

发表评论取消回复