首页 > 其他分享 >长链剖分

长链剖分

时间:2023-08-25 18:56:13浏览次数:28  
标签:长链 剖分 idx int up down

例题:

P5903 【模板】树上 k 级祖先

题目描述

image

思路

长链剖分模板题。

长链剖分:

  1. 计算 \(f[i][j]\) 表示 \(i\) 的 \(2^j\) 级祖先;
  2. 计算 \(up[i][j]\) 表示 \(i\) 的 \(j\) 级祖先;
  3. 计算 \(down[i][j]\) 表示在长链上从 \(i\) 向下走 \(j\) 步到达的祖先。
  4. 计算 \(i\) 的 \(k\) 级祖先,先让 \(i\) 跳到 \(2^\left\lfloor \log_2k \right\rfloor\) 级祖先,\(k\) 减去 \(2^\left\lfloor \log_2k \right\rfloor\),再让 \(i\) 跳到长链顶端,\(k\) 减去 \(dep[i] - dep[top[i]]\),最后如果 \(k \ge 0\),那么答案就是 \(up[i][k]\),否则 \(k < 0\),答案就是 \(down[i][-k]\)。

代码

// Problem: P5903
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5903
// Memory Limit: 500 MB
// Time Limit: 3000 ms


#include <bits/stdc++.h>

using namespace std;
using uint = unsigned int;

#define int long long

const int N = 500010, M = 20;

struct edge {
	int to, next;
} e[N];

int head[N], idx;

void add(int u, int v) {
	idx++;
	e[idx].to = v;
	e[idx].next = head[u];
	head[u] = idx;
}

int n, q, s;

uint get_rand(uint x) {
	x ^= x << 13;
	x ^= x >> 17;
	x ^= x << 5;
	return s = x;
}

int rt;
int fa[N][M];

void initfa() {
	for (int j = 1; j < M; j++) {
		for (int i = 1; i <= n; i++) {
			fa[i][j] = fa[fa[i][j - 1]][j - 1];
		}
	}
}

int dep[N], ds[N], son[N];

void dfs(int u) {
	dep[u] = ds[u] = dep[fa[u][0]] + 1;
	for (int i = head[u]; i; i = e[i].next) {
		int to = e[i].to;
		dfs(to);
		if (ds[to] > ds[u]) {
			ds[u] = ds[to];
			son[u] = to;
		}
	}
}

vector<int> up[N];
vector<int> down[N];
int belong[N];

void init(int u, int p) {
	belong[u] = p;
	if (u == p) {
		int tmp = u;
		for (int i = 0; i <= ds[u] - dep[u]; i++) {
			up[u].push_back(tmp);
			tmp = fa[tmp][0];
		}
		tmp = u;
		for (int i = 0; i <= ds[u] - dep[u]; i++) {
			down[u].push_back(tmp);
			tmp = son[tmp];
		}
	}
	if (son[u]) init(son[u], p);
	for (int i = head[u]; i; i = e[i].next) {
		int to = e[i].to;
		if (to == son[u]) continue;
		init(to, to);
	}
}

int query(int u, int k) {
	if (!k) return u;
	u = fa[u][__lg(k)];
	k -= 1 << (__lg(k));
	k -= dep[u] - dep[belong[u]];
	u = belong[u];
	if (k >= 0) return up[u][k];
	else return down[u][-k];
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> q >> s;
	for (int i = 1; i <= n; i++) {
		cin >> fa[i][0];
		if (!fa[i][0]) rt = i;
		if (fa[i][0]) add(fa[i][0], i);
	}
	initfa();
	dfs(rt);
	init(rt, rt);
	
	int ans = 0, res = 0;
	int x, k;
	for (int i = 1; i <= q; i++) {
		x = ((get_rand(s) ^ ans) % n) + 1;
		k = ((get_rand(s) ^ ans) % dep[x]);
		ans = query(x, k);
		res ^= (i * ans);
	}
	cout << res << '\n';
	return 0;
}

标签:长链,剖分,idx,int,up,down
From: https://www.cnblogs.com/Yuan-Jiawei/p/17657737.html

相关文章

  • 树链剖分学习(复习?)笔记
    树链剖分,即树剖。顾名思义,树链剖分就是将一棵树通过某种方式剖分成若干条链,再利用\(dfs\)序,从而将树上的问题转化为序列上的问题。树剖的方式有不止一种,比如重链剖分、长链剖分。最常用的(大概?)是重链剖分。此处介绍重链剖分。首先,我们定义一个节点的重儿子为此节点的所有儿......
  • 树链剖分/重链剖分模板
    #include<bits/stdc++.h>usingnamespacestd;intn,m,d,mod,w[200005],wt[200005],e[200005],ne[200005],h[200005],idx=1,t[800005],l[800005],r[800005],tag[800005];intson[200005],id[200005],fa[200005],cnt,dep[200005],siz[200005],top[200005];/*son[]重儿子......
  • 『复习笔记』树链剖分(重链剖分)
    前言(事出必有因)今天模拟赛有一道线段树+LCA的题,考场上码了两个小时,结果pushup错了,结果线段树调完了,发现TLE了,原来是求LCA炸了。。因为我用的倍增(我就是倍增狗你能把我怎么样),但是倍增的一个重要问题就是log都跑满了,但是树剖跑不满log,别问我为什么不用Tarjan,因为这题是在线的不好......
  • 树链剖分 | 洛谷 P4114 Qtree1
    前言题目链接:洛谷P4114Qtree1前置知识:树链剖分题意给定一棵树,有修改边权和查询两点之间边权最大值两种操作,对于每个查询输出结果。解析已经在前置博客里提到,树链剖分可以将树上的任意一条路径划分成不超过\(O(\logn)\)条连续的链,保证划分出的每条链上的节点DFS序......
  • 树链剖分详解
    目录前言一、树剖是什么?二、重链剖分树剖的实现例题总结前言在同学们一路走来的过程中,一定已经学习了倍增求LCA的算法。倍增求LCA算法只适用于少部分情况,那么,如果要求在求出LCA的同时,对两点\(a,b\)之间的所有点权(或边权)进行求和或修改,又该怎么做呢?这里介绍一种树链......
  • 杭电23多校第九场Capoo on tree(二分+树链剖分+可持久化线段树)
    2023HDU多校9__Capooontree(二分+树链剖分+可持久化线段树)题目链接Solution\(Hint1\)考虑如何进行对某一相同点权的所有点进行点权\(+1\)操作,如果我们建立权值线段树,那只需要将权值为\(x\)的点并入权值\(x+1\)即可,但是这样就算我们建立以节点编号为版本的可持久化线段树,也是......
  • URL长链接转短链接
    一、短链接技术1.简介短链接技术是一种将长URL映射为短URL的技术。简单来说,就是通过一个简化的算法,将输入的长URL转换为一个短URL字符串,这个字符串可以按照短URL本身的需求进行设计,比如可以使用一定的字符集,并且限制字符串长度。2.短链接的优点短链接技术的主要优点包......
  • VTK 实例58:三角剖分(表面重建)
    1#include<vtkAutoInit.h>2VTK_MODULE_INIT(vtkRenderingOpenGL2);3VTK_MODULE_INIT(vtkRenderingFreeType);4VTK_MODULE_INIT(vtkInteractionStyle);56#include<vtkSmartPointer.h>7#include<vtkProperty.h>8#include<vtkPo......
  • VTK 实例59:加入边界限制的三角剖分(表面重建)
    1#include<vtkAutoInit.h>2VTK_MODULE_INIT(vtkRenderingOpenGL2);3VTK_MODULE_INIT(vtkRenderingFreeType);4VTK_MODULE_INIT(vtkInteractionStyle);56#include<vtkSmartPointer.h>7#include<vtkProperty.h>8#include&......
  • 树链剖分
    引入维护一棵树,支持两种操作改变边权|边权询问路径中最大权(或其他)BF的期望是\(O(\logn)\),但是容易退化成\(O(n)\),所以引入树链刨分,这里用轻重链刨分轻重链刨分记\(SIZE_i\)表示以\(i\)为根的子树的节点个数,那么对于\(x\)为的子节点\(y\),若\(SIZE_y\)......