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

树链剖分

时间:2024-10-31 17:41:37浏览次数:1  
标签:线段 剖分 树剖 dep top 树链 LCA 节点

轻重链剖分

性质

重链

重链内编号连续,可以用线段树维护一些值

路径

对于树上任意两点\(x,y\),它们的路径经过的重链不超过\(logn\)条

树剖正是运用这种方式,把1个修改/询问变成\(logn\)个修改/询问,然后高效求解

注意:树剖的作用是将树上问题拆成\(logn\)个序列问题,并不是所有树剖都一定要用线段树,只要能对序列问题进行高效维护就行了

子树

子树内编号连续(其实任意子树的\(dfn[]\)都是连续的),对于子树内统计求和可以用线段树实现

注意这里只是用了树剖的编号思想,实际做题不一定用得到

细节实现

跳链时深度判断:dep[top[x]]<dep[top[y]]

如在路径加权时:

void Line_plus(int x,int y,int k) {
	while(top[x]!=top[y]) {
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		Plus(1,1,n,k,num[top[x]],num[x]);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	Plus(1,1,n,k,num[x],num[y]);
}

如果第三行的dep[top[x]]<dep[top[y]]写成了dep[x]<dep[y],就会导致x会跳到0,导致线段树死循环(L,R其中一个为0)

如图,dep[x]>dep[y]如果x先跳,会使x直接跳出树

P4211 [LNOI2014]LCA

模型:\(\sum_{i=1}^ndep(LCA(i,x))\)

考虑改变\(dep(LCA(x,y))\)的意义:\(LCA(x,y)\)走到根节点所经过的点的数量

如果我们对\(y\)走到根节点经过的点染色,那么\(x\)走到根节点经过的有颜色的点的数量,刚好为\(LCA(x,y)\)走到根节点所经过的点的数量

计算多点与\(x\)的\(LCA\)时,我们考虑多点同时“染色”,再让\(x\)“走”到根节点,即每个点对到根节点的路径权值加\(1\),再统计\(x\)到根的路径权值和

P5305 [GXOI/GZOI2019]旧词

前一题的加强版(但是完全没加强但是我没想到看题解又看了半天才理解,我是sb)))

即用线段树维护:

1、区间\([l,r]\)每个数加上\(dep_i^k-(dep_i-1)^k\)

2、查询区间\([l,r]\)的数的和

题解中说的预处理区间权值和的区间其实是线段树的结点\(x\)控制的区间\([l,r]\),即区间\([l,r]\)全被打标记时直接用预处理的数更新\(sum[]\),然后上传

写这段解释时更加感觉没想出来的我是sb

标签:线段,剖分,树剖,dep,top,树链,LCA,节点
From: https://www.cnblogs.com/zhone-lb/p/18518534

相关文章

  • 树链部分
    说句闲话这个东西已经20多天没写了,感觉已经忘没了,非常糟糕,只好赶快补一补,确实还是得多打代码,不然都忘光就丸辣。前言树链问题通常是关于树上路径的操作,将路径拆分成一条条链,然后用线段树维护链的权值。注:本题解并不适用于毫无基础的oier,只是做简单讲解,想了解具体定义请自行查......
  • CF1249F Maximum Weight Subset 题解 / 长链剖分复习
    CF1249FMaximumWeightSubset题解题目大意给定一个\(n\)个节点的树,每个节点有点权\(a_i\)。从中选出若干节点,要求这些点两两之间距离大于给定常数\(k\),使得点权和最大。Solve给出一种线性做法。前置知识:长链剖分优化DP。考虑一个DP:设\(f(u,d)\)表示在\(u\)的子......
  • 树链剖分
    树链剖分重链剖分【问题引入】问题描述给定一颗有$n$个节点、带边权的树,现在有对树进行$m$个操作,操作有$2$类:将节点$a$到节点$b$路径上所有边权的值都改为$c$;询问节点$a$到节点$b$路径上的最大边权值。请你写一个程序依次完成这$m$个操作。有三个操作......
  • 长链剖分 入门
    长链剖分额,其实和树剖差不多,对于每个节点\(u\)维护\(mxd_u\)为子树内节点深度最大值。那么令\(Son(u)\)里取到\(mxd_v\)最大的儿子\(v\)为长儿子,类似重链剖分处理即可。同样令连接不同长链的两个点之间的边为虚边。有如下性质:从根到节点\(u\),所经过虚边个数不超......
  • 【算法】树链剖分
    1.算法简介树链剖分为将树分割成若干条链,维护树上信息的思想。通常将其分为链后能用数据结构维护。树链剖分分为重链剖分,长链剖分,实链剖分。通常重链剖分最常用,本文主要介绍重链剖分。重链剖分可将树划分为一个个长度不超过\(O(\logn)\)的链,并且保证每条链内的\(dfs\)序......
  • 树链剖分笔记
    题单传送门2024.10.12P3038GrassPlantingG:DevC++栈空间开小了;调了三天啊三天线段树区间修改写成区间单点修改了;树剖往上跳写成了dep[u]<dep[v]而不是dep[top[u]]<dep[top[v]]2024.10.15P3128MaxFlowP:奇怪的TLE树剖DFS没把子树大小加到根上,重链剖分写成了后......
  • 树链剖分|树上启发式合并
    树链剖分分为重链剖分和长链剖分以及其他奇怪的剖分。以重剖为主。重链剖分将树上问题重链剖分为序列问题(经常是DFS序)然后用数据结构(经常是线段树)维护。剖分部分定义:重儿子:对于一个点,其儿子中,子树最大的那个;重边:父亲到重儿子的连边;轻儿子:除了重儿子以外的儿子;轻边:父亲......
  • 树链剖分
    考一遍,学一遍,忘一遍这里是重链剖分。两个dfs,第一个找重儿子,第二个找重链顶和dfn(注意要优先对重儿子dfs来保证同一条重链上的dfs序连续)查询和维护时一个一个跳重链顶端,时间复杂度O(nlogn)。常和线段树配套使用。模板#include<bits/stdc++.h>#definelllonglong#defineli......
  • [OI] 树链剖分
    学的时候比较朦胧,现在不朦胧了,所以写一下讲解重儿子:一个节点的子树大小最大的儿子轻儿子:非重儿子重链:节点->重儿子->重儿子..这样的链AbeautifulTree蓝线为重链可以发现,树上的所有节点一定属于且仅属于一个重链首先要知道如何找重链这很简单,可以通过一遍DFS......
  • [学习笔记]树链剖分(简易版) 及其LCA
    树链剖分先讲解一下一些基础定义(都是在树上)重儿子:一个节点中所有儿子中子树大小最大的一个儿子(每个节点最多有一个重儿子)轻儿子:一个节点除重儿子外所有的节点重链:若干个重儿子组成的链链顶:一条链中深度最小的节点以下图为例子(红色连续线段为重链)对于节......