树论LCTclassC_LinkCutTree{public: intrev[N],fa[N],ch[N][2]; /*====================*/ boolWhich(intx) { returnch[fa[x]][1]==x; } boolIsRoot(intx) { returnch[fa[x]][Which(x)]!=x; } /*====================*/ voidPushUp(intx) {

P3320[SDOI2015]寻宝游戏小B最近正在玩一个寻宝游戏，这个游戏的地图中有\(N\)个村庄和\(N-1\)条道路，并且任何两个村庄之间有且仅有一条路径可达。游戏开始时，玩家可以任意选择一个村庄，瞬间转移到这个村庄，然后可以任意在地图的道路上行走，若走到某个村庄中有宝物，则视为找到该

在“无限”的量中寻找“有限”的量——可能产生贡献的点对的数量不妨用两个log的时间复杂度进行预处理（都预处理了，就不要再想着判断合法性了）1~N每个数的约数个数的总和大约为NlogNu,v都在某个子树内等价于它们的【最近公共祖先】在该子树内，将点对的贡献打到LCA(i,j)上点击查

MilkVisitsG自己做出来哒！先考虑是一条链时怎么做。很显然，用set维护每种奶的位置，然后lowerbound查找\(l\)再判断是否合法即可。那么再放到树上来做，显然，直接树链剖分就可以把树转化成链。于是做完力！点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintN

P5642人造情感（emotion）随便挑点杂题做/kk。乐。不会做这个题，我难道还不会做CF856DMashaandCactus。先考虑后者怎么做？CF856DMashaandCactus乐。考虑在\(LCA\)上挂很多个chains.\[s_u=\sum_{v\inson_u}f_v,f_u=s_u\]\[t_i=\underset{(x_i,y_i,w_i)}

目录RMQ问题ST表优缺点实现递推查询复杂度代码技巧-快速读入RMQ问题RMQ（RangeMaximum/MinimumQuery）问题，即区间最值问题。一般是多次询问，对时间复杂度要求高，一般需要\(O(logn)\)或\(O(1)\)复杂度ST表p[i][j]是以i为起点，连续\(2^j\)个数字的最大值(是一个递推表)3

cmd的blog可以参考水平不高,内容比较简单.内容难度不随章节单增.0.杂七杂八做题做到什么东西都会扔到这里.想到啥写啥.如果要求统计树上所有点对之间的贡献,可以考虑枚举lca.(CF1856E1)如果有类似于树上经过的边的权值\(\leqk\)这样的限制,可以把边按照边

生生动动贺题贺一遍！考虑先求出\(f_x\)表示\(x\)子树大小\(\leq\frac{n+1}{2}\)的方案数。最后再容斥掉\(x+1\ton\)的方案即可。\[\sum^{n-x+1}_{j=\frac{n+1}{2}}\binom{n-i}{j-1}(j-1)!(n-j-1)!(i-1)\]即考虑选出子树，生成子树内和子树

前言：输了，被水杯提醒我一直很失败。正片：简要题意求\([l,r]\top\)的路径的交的边权和。Solution：\(O(n\log^2n)\)巨大分讨做法。考虑分类讨论。其一，\(p\)根本就不属于路径上的点，这个求区间LCA可以解决\(p\toanc_{[l,r]}\)其二，\(p\)是\(anc_{l,r}\)的祖

悲报：335->220战绩:100+100+20+0T1求子树sizeT2通过大眼观察严谨的证明后，我们发现\(x_i\)是\(x_i+1\)的祖先的概率和\(x_i+1\)具体是什么无关：我们令\(x_i+1\)一直跳父亲，直到编号小于等于\(x_i\)的那一次。因为父亲是等概率选取的，所以概率就是\(\frac{1}{x_i}\)

1.重链剖分1.1.简介重链剖分将树分割成若干链维护信息，将树的结构转换为线性结构，然后可用其他数据结构维护。定义以下概念：重子节点轻子节点重边轻边重链某节点的子节点中子树大小最大的那个某节点的子节点中的非重子节点由某节点到其重子节点的连边由某节点到

一、最近公共祖先最近公共祖先二、树链剖分重链剖分长链剖分三、树分治点分治点分树四、计数问题Prufer序列

本文包含树的定义,树的存储,树的遍历(包括定义,求法).基础定义我们把\(n\)个点,\(n-1\)条边的图称为树.特别情况对于树,存在部分情况,使其有着特殊的性质

我们假设你已经熟练掌握了树上的各项基础技术.下面来做一下题吧!1.[NOIP2007提高组]树网的核简明题意:给定一棵有\(n\)个结点的带权无根树,在其直径上找到一段长

关于树上的路径\(a_1\toa_2\toa_3\toa_4\to...\toa_n\)（\(a_i\)与\(a_{i+1}\)之间未必有边，路径可重复）的路径并处理问题如果我们面临多次询问，每次给你一堆

LCA与树上差分轻重链剖分长链剖分树分治

复习清单。现在发现套路题也切不动了。板子也相当生疏。开始复习。大体是图论\(\rightarrow\)数学\(\rightarrow\)字符串\(\rightarrow\)树论\(\rightarrow\)dp

树上倍增树上倍增其实可以类比为树上二分，不断的去逼近答案。也没有什么好说的直接看题吧。例\(1.1\)：Tree-洛谷最近公共祖先LCA求法大致有三种：倍增\(lca\)，\(Tarjan