【数据结构题目讲解】BZOJ 3306 - 树 利用DFS序求解

这篇具有很好参考价值的文章主要介绍了【数据结构题目讲解】BZOJ 3306 - 树 利用DFS序求解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

BZOJ 3306 - 树

D e s c r i p t i o n \mathrm{Description} Description

给定 1 1 1 棵以 1 1 1 为根节点的 n n n 个点的树,接下来有 m m m 次操作:

  • V x y x x x 点的权值更改为 y y y
  • E x 将根改为 x x x
  • Q x 查询 x x x 子树的最小值

S o l u t i o n \mathrm{Solution} Solution

首先,考虑如果没有换根操作(即 E 操作),那么直接使用 DFS 序配合线段树的方式即可解决。

DFS 序

对于 1 1 1 棵树的 DFS 序,一个子树在 DFS 序中一定是连续的一个区间:

【数据结构题目讲解】BZOJ 3306 - 树 利用DFS序求解,数据结构经典,数据结构,算法,c++

这棵树的 DFS 序即为:1 2 4 5 3DFS 序就是 DFS 的过程中点访问的先后顺序)

比如说:此时考虑 2 2 2 节点的子树,那么在 DFS 序上即为区间 [ 2 , 4 ] [2,4] [2,4]。也就是说,对于 i i i 号节点的子树,在 DFS 序上为 [ P i , P i + S z i − 1 ] [P_i,P_i+Sz_i-1] [Pi,Pi+Szi1],其中 P i P_i Pi 表示 i i i 节点在 DFS 序中的位置, S z i Sz_i Szi 表示 i i i 子树的大小。

那么,既然是 1 1 1 个区间,所以就可以使用线段树进行快速求解。


那么,就可以由查询子树最小值转化为查询区间最小值。

这时候,考虑换根操作,我们考虑对于某些子树,换根之后,它的子树会不会发生改变。

比如说:

【数据结构题目讲解】BZOJ 3306 - 树 利用DFS序求解,数据结构经典,数据结构,算法,c++

当以 x x x 为根时, y y y 子树会发生变化吗?手绘可以发现,其实并不会发生任何变化,所以按照原根进行计算。

那如果 y y y x x x 的子树内部呢?

【数据结构题目讲解】BZOJ 3306 - 树 利用DFS序求解,数据结构经典,数据结构,算法,c++

比如说,这样:通过重新画树即可发现,其实 y y y 的子树根本未发生变化!所以这 2 2 2 种位置的子树都不会发生变化。

那,什么时候会发生变化呢?还是说,永远都不会发生变化?

其实,漏考虑了 1 1 1 种情况,即为 y y y x x x 到原根的路径上:

【数据结构题目讲解】BZOJ 3306 - 树 利用DFS序求解,数据结构经典,数据结构,算法,c++

比如说这样,手绘之后发现, y y y 的子树确实发生变化了,其实就是 x x x 子树外的部分。

进一步讨论,如果 y y y 在原根上呢?(图就不给了)这时候其实是少了上图 y y y 的位置的子树。

综上所述:文章来源地址https://www.toymoban.com/news/detail-826762.html

  • 只有子树的根节点在原根到换之后的根之间的路径上,才会有变化,此时子树为所有点减去 y y y 到换之后的根之间的路径上与 y y y 相邻的点 ,即为 z z z。(在 DFS 序上其实就是 2 2 2 段,即除了 z z z 子树的部分)
  • 反之,按照原根进行计算即可。
#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int SIZE = 1e5 + 10, INF = 1e18;

int N, Q;
int Root, A[SIZE];
std::vector<int> G[SIZE], DFS_Order;
int Depth[SIZE], Fa[SIZE][32], Pos[SIZE], Sz[SIZE];

void BFS(int root)
{
    memset(Depth, 0x3f, sizeof Depth);
    queue<int> q;
    q.push(root);
    Depth[0] = 0, Depth[root] = 1;

    while (q.size())
    {
        int t = q.front();
        q.pop();

        for (auto j : G[t])
            if (Depth[j] > Depth[t] + 1)
            {
                Depth[j] = Depth[t] + 1;
                q.push(j);
                Fa[j][0] = t;
                for (int k = 1; k <= 22; k ++)
                    Fa[j][k] = Fa[Fa[j][k - 1]][k - 1];
            }
    }
}

int LCA(int a, int b)
{
	if (Depth[a] < Depth[b]) swap(a, b);
    for (int k = 22; k >= 0; k --)
        if (Depth[Fa[a][k]] >= Depth[b])
            a = Fa[a][k];

    if (a == b) return a;

    for (int k = 22; k >= 0; k --)
        if (Fa[a][k] != Fa[b][k])
            a = Fa[a][k], b = Fa[b][k];

    return Fa[a][0];
}

void DFS(int u, int fa)
{
	DFS_Order.push_back(u), Pos[u] = DFS_Order.size() - 1;
	Sz[u] = 1;
	for (auto c : G[u])
	{
		if (c == fa) continue;
		DFS(c, u);
		Sz[u] += Sz[c];
	}
}

struct Segment
{
	int l, r;
	int Min;
}Tree[SIZE << 2];

void Pushup(int u)
{
	Tree[u].Min = min(Tree[u << 1].Min, Tree[u << 1 | 1].Min);
}

void Build(int u, int l, int r)
{
	if (l == r)
	{
		Tree[u] = {l, l, A[DFS_Order[l]]};
		return;
	}

	Tree[u] = {l, r};
	int mid = l + r >> 1;
	Build(u << 1, l, mid), Build(u << 1 | 1, mid + 1, r);
	Pushup(u);
}

void Modify(int u, int x, int d)
{
	if (Tree[u].l == Tree[u].r && Tree[u].l == x)
	{
		Tree[u].Min = d;
		return;
	}

	int mid = Tree[u].l + Tree[u].r >> 1;
	if (mid >= x) Modify(u << 1, x, d);
	else Modify(u << 1 | 1, x, d);
	Pushup(u);
}

int Query(int u, int l, int r)
{
	if (Tree[u].l >= l && Tree[u].r <= r)
		return Tree[u].Min;

	int mid = Tree[u].l + Tree[u].r >> 1, Result = INF;
	if (mid >= l) Result = Query(u << 1, l, r);
	if (mid < r) Result = min(Result, Query(u << 1 | 1, l, r));
	return Result;
}

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> N >> Q;

	int F;
	for (int i = 1; i <= N; i ++)
	{
		cin >> F >> A[i];
		if (!F) Root = i;
		else G[i].push_back(F), G[F].push_back(i);
	}

	BFS(Root);
	DFS_Order.push_back(-1), DFS(Root, -1);
	Build(1, 1, N);

	while (Q --)
	{
		char Op;
		int x, y;

		cin >> Op >> x;

		if (Op == 'V')
		{
			cin >> y;
			Modify(1, Pos[x], y);
		}
		else if (Op == 'E')
			Root = x;
		else
		{
			if (x == Root)
				cout << Query(1, 1, N) << endl;
			else if (LCA(Root, x) == x && Depth[Root] >= Depth[x])
			{
				for (auto v : G[x])
					if (LCA(v, Root) == v && Depth[v] >= Depth[x])
					{
						int Result = INF;
						if (Pos[v] > 1) Result = min(Result, Query(1, 1, Pos[v] - 1));
						if (Pos[v] + Sz[v] <= N) Result = min(Result, Query(1, Pos[v] + Sz[v], N));
						cout << Result << endl;
						break;
					}
			}
			else
				cout << Query(1, Pos[x], Pos[x] + Sz[x] - 1) << endl;
		}
	}

	return 0;
}

到了这里,关于【数据结构题目讲解】BZOJ 3306 - 树 利用DFS序求解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C语言&&数据结构】简单题目

    ✨作者:@平凡的人1 ✨专栏:《小菜鸟爱刷题》 ✨一句话:凡是过往,皆为序章 ✨说明: 过去无可挽回, 未来可以改变 为了方便自己的学习以及基于好久没更新博客的原因。特地写了这一篇博客 。💖 本篇博客是一篇记录学习篇,我将之归纳于刷题专栏。方便自己的复习以

    2023年04月08日
    浏览(51)
  • 【数据结构】二叉树经典题目

    相信大部分人看了题目描述之后,都会和我一样一脸的懵逼。直到我看到了一个描述才恍然大悟 分为3种情况: 左右都为空 --省略 右为空,左不为空 – 省略 左为空,右不为空–不省略 这里复习一下二叉树的前序遍历、中序遍历、和后序遍历 前序的结果是:ABDEGCF 中序的结

    2024年02月10日
    浏览(54)
  • 【数据结构】二叉树常见题目

    此乃本人自用版本,用于复习回顾! 所以部分题目不会有过大详细的解析,不懂的可以评论!笔者将竭力为你解答 满⼆叉树:如果⼀棵⼆叉树只有度为0的结点和度为2的结点,并且度为0的结点在同⼀层上,则这棵⼆叉树为满⼆叉树 高度为h的满二叉树,共有 2^h -1 个节点 完全

    2024年02月13日
    浏览(38)
  • 【数据结构】栈和队列常见题目

    队列:先进先出 栈:后进先出 队列:先进先出 栈:后进先出 https://leetcode.cn/problems/valid-parentheses/ 做法:遍历字符串 1.当前字符是左括号:进栈 2.当前字符是右括号:出栈顶元素和当前字符比较是否匹配 特殊情况:如果此时栈为空,那么说明不匹配 3.最后如果栈为空,说明

    2024年02月12日
    浏览(37)
  • 【数据结构——有向图】有环无环判定、拓扑排序(DFS、BFS)

    有向图(Directed Graph),也被称为有向图形或方向图,是一种图的类型。在有向图中,图中的边具有方向,从一个顶点指向另一个顶点。 在有向图中,每个顶点表示一个实体,而有向边则表示实体之间的关系或连接。这种有方向性的边表明了连接的起点和终点之间的单向关系

    2024年02月09日
    浏览(49)
  • 数据结构——图解链表OJ题目

            学完了单链表之后,我们对其基本结构已经有了一定的了解,接下来我们通过一些题目强化对链表的理解,同时学习一些面试笔试题目的新思路以及加强对数据结构单链表的掌握。  目录 题目一.876. 链表的中间结点 - 力扣(LeetCode) 题目二:21. 合并两个有序链表

    2024年02月04日
    浏览(65)
  • 【数据结构】链表相关题目(中档题)

    🚀write in front🚀 📜所属专栏:初阶数据结构 🛰️博客主页:睿睿的博客主页 🛰️代码仓库:🎉VS2022_C语言仓库 🎡您的点赞、关注、收藏、评论,是对我最大的激励和支持!!! 关注我,关注我,关注我 , 你们将会看到更多的优质内容!!   在前面的练习中,我们简

    2024年01月22日
    浏览(44)
  • 【数据结构】链表相关题目(简单版)

    🚀write in front🚀 📜所属专栏: 初阶数据结构 🛰️博客主页:睿睿的博客主页 🛰️代码仓库:🎉VS2022_C语言仓库 🎡您的点赞、关注、收藏、评论,是对我最大的激励和支持!!! 关注我,关注我,关注我 , 你们将会看到更多的优质内容!!   在学完了顺序表的基本

    2024年01月19日
    浏览(46)
  • 数据结构与算法大作业:走迷宫程序(C语言,DFS)(代码以及思路)

    好家伙,写大作业,本篇为代码的思路讲解   问题描述: 以一个 m * n 的长方阵表示迷宫, 0和1分别表示迷宫的通路和障碍。 设计一个程序, 对任意设定的迷宫, 求出一条从入口到出口的通路, 或得出没有通路的结论。 基本要求: (1) 实现一个以链表做存储的栈类型,

    2024年02月03日
    浏览(42)
  • 【数据结构】图的创建(邻接矩阵,邻接表)以及深度广度遍历(BFS,DFS)

    图是由顶点集合及顶点间的关系组成的一种数据结构:G = (V, E),其中: 顶点集合V = {x|x属于某个数据对象集}是有穷非空集合; E = {(x,y)|x,y属于V}或者E = {x, y|x,y属于V Path(x, y)}是顶点间关系的有穷集合,也叫 做边的集合。 完全图:在有n个顶点的无向图中,若有n * (n-1)/2条边,

    2024年02月04日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包