树链专题
SPOJ - QTREE (树链剖分)
基础的树链剖分题目，不过是边权，可以向下映射成点权或者按边剖分。 VIEW CODE #include <iostream>#include<stdio.h>#include<cmath>#include<string.h>#include<algorithm>#include<string>using namespace std;const int mmax=100
![[HDU 5029] Relief grain （树链剖分+线段树）](/front/images/it_default.jpg)
[HDU 5029] Relief grain （树链剖分+线段树）
HDU - 5029 其实这道题最大的难点不是树链剖分，而是怎么维护某个点被那些颜色染过，染过多少次 如果在线段树维护的话，很难做到，估计得树套树，而且空间会炸 好在这题是离线的，可以使用差分的思想来维护 对一段区间[l,r]染色 c，相当于在这段区间左端点 l打上 c标志，右端点 r+1打上 -c标志 然后扫一遍整个区间 （依照 dfs序扫一遍整棵树），期间不断维护一颗线段树 线段树
HDU 3966 Aragorn's Story 树链剖分
入门题 #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 50010;struct edge{int v, next;}e[maxn*2];int n, m, q;int first[maxn], cnt;int top[maxn], tid[
poj3237 Tree 树链剖分
题意：在spoj375基础上增加了一条路径的取反操作，其他都一样。 思路：剖分没有变化，在线段树部分，需要一个tag标记该段是否需要需要取反，记录一个最大值、最小值即可。= =（打tag的那 段应该已经跟新好，push_down的时候如果tag=1那么直接对两个子段进行更新。。一开始意识模糊了。。）详见代码： /************************************
fzu2082 过路费 树链剖分
题意：中文题。。 思路：树链剖分后，在线段树上单点更新，区间查询。详见代码： /*********************************************************file name: fzu2082.cppauthor : kereocreate time: 2015年01月21日 星期三 09时21分42秒***********************
hdu 4897 Little Devil I(树链剖分+线段树)
题目链接：hdu 4897 Little Devil I 题目大意：给定一棵树，每条边有黑白两种颜色，初始都是白色，现在有三种操作： 1 u v：u到v路径上的边都取成相反的颜色2 u v：u到v路径上相邻的边都取成相反的颜色（相邻即仅有一个节点在路径上）3 u v：查询u到v路径上有多少个黑色边 解题思路：树链剖分，用两个线段W和L维护，W对应的是每条的黑白情况，L表示的是每个节点
hdu 5029 Relief grain(树链剖分+线段树)
题目链接：hdu 5029 Relief grain 题目大意：给定一棵树，然后每次操作在uv路径上为每个节点添加一个数w，最后输出每个节点个数最多的那个数。 解题思路：因为是在树的路径上做操作，所以基本就是树链剖分了。只不过以前是用一个数组即可维护值，这题要用 一个vector数组记录。过程中用线段树维护最大值。 #pragma comment(linker, "/STA
Codeforces 191C Fools and Roads(树链剖分)
题目链接：Codeforces 191C Fools and Roads 题目大意：给定一个N节点的数，然后有M次操作，每次从u移动到v，问说每条边被移动过的次数。 解题思路：树链剖分维护边，用一个数组标记即可，不需要用线段树。 #include <cstdio>#include <cstring>#include <algorithm>using namespace std;c
spoj 375. Query on a tree(树链剖分)
题目链接：spoj 375. Query on a tree 题目大意： poj 3237的简化版，用同一份代码都能过。 解题思路：略。 #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 10005;const int INF = 0x3f3
Light OJ 1348 - Aladdin and the Return Journey(树链剖分)
题目链接：Light OJ 1348 - Aladdin and the Return Journey 题目大意：给定一棵树，两种操作 0 i j：ij路径上的权值和1 i v：将第i个节点的权值修改为v 解题思路：树链剖分的裸题。 #include <cstdio>#include <cstring>#include <algorithm>using namespace std
hdu 3966 Aragorn's Story(树链剖分+树状数组)
题目链接：hdu 3966 Aragorn's Story 题目大意：给定一个棵树，然后三种操作 Q x：查询节点x的值I x y w：节点x到y这条路径上所有节点的值增加wD x y w：节点x到y这条路径上所有节点的值减少w 解题思路：树链剖分，用树状数组维护每个节点的值。 #pragma comment(linker, "/STACK:1024000000,1024000000
hdu 5458 Stability(树链剖分+强连通缩点+线段树)
题目链接：hdu 5458 Stability 解题思路 先将操作处理一遍，获得最终图，然后对图进行双联通缩点，剩下的肯定是一棵树，然后将操作逆着做一遍，遇到删边等于是加一条边，加的这条边u，v等于是将两节点路径上的点联通起来变成一个新的双联通分量，在同一个双联通分量中，明显ans=0。所以我们用线段树维护树的每条边权，一开始全为1，每次添加一条边，就将这条路径上的边权值置为0。 代码 #
hdu 5452 Minimum Cut(树链剖分)
题目链接：hdu 5452 Minimum Cut 解题思路 因为有一条一定要在给定的树上，所以我们可以求出切某条树边时，最少还需要再切割几条边可以使得该树边联通的两个点集不联通。先对给定的树做树链剖分，然后对剩余的非树边u，v，更新路径u-v上边的权值，加1。 代码 //#pragma comment(linker, "/STACK:1024000000,1024000000")#in
FZOJ 2176 easy problem ( 树链剖分 )
题目链接~~> 做题感悟：感觉做多了树链剖分的题目，有许多是树链剖分 + 想法。。 解题思路： 这题很明显的一点就是 k 很小，那就是告诉你可以从 k 入手，怎样入手呢 ？ 观察可以发现无非最多是 k 类点 ，0 ~ k-1 ,分别表示与根的距离模 k .这样就可以把点分类加权值，但是每个线段树里存的还是所有元素，查询的时候对应查找。 代码： #in
24.5.26（树链剖分板子，二分+线段树）
星期一： 补重庆科技 C 二分 牛客传送门 思路：二维前缀和表示到第 i个人第 j个弹巢开了多少发，和st【i】表示第 i个人开的是第几个弹巢 对于 l和r的查询，使用前缀和二分找出第一个中枪的人，但因为题意第 l个人开的是1号弹巢，所以弹巢编号会有一个偏移，例如st【l】==5，那么偏移量就为4
树链剖分详解，看这一篇就够了
前置知识： 树形结构链式前向星(熟练)线段树(熟练)DFS序(熟练)LCA(了解定义) 什么是树链剖分 树链剖分其实有两种：重链剖分和长链剖分。重链剖分就是把儿子节点最重的儿子称为重儿子，把树分成若干条重链（如图一）； 图一 长链剖分则是把深度差最大的儿子称为长儿子，把树分成若干条长链（如图二）： 图二 树链剖分的应用非常广泛，一般用的都是重链剖
HDU5274 Dylans loves tree（树链剖分）很巧的点权更新
Dylans loves tree Accepts: 49 Submissions: 262 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) 问题描述 Dylans有一棵N个点的树。每个点有点权。树上节点标号为1∼N。他得到了Q个询问，形式如下：
HYSBZ - 2243染色——树链剖分+线段树建树技巧
【题目描述】 HYSBZ - 2243染色 【题目分析】 我一直没有看清楚题，以为求的是路径上出现颜色的种类，然后就写了一个区间染色的线段树进行维护，过样例的时候才发现题读错了，人家要求的是路径上出现的颜色段，所以颜色的种类不重要，重要的是每一段每一段。理所当然，我们应该用线段树维护所在区间有多少段。但是左右区间上传的时候如果边界颜色相同（左节点的右边界和右节点的左边界），那么区间个数应该减一。
树链剖分+线段树【SDOI2011】 bzoj2243 染色
题目大意： 给一棵树，每个节点有一个颜色。写一个程序支持把两个点路径上的所有点染成一个颜色，查询两点之间的色段数量。 解题思路： 树链剖分+线段树 首先它是一颗树，而且是修改和查询两点路径上的颜色，可以想到树链剖分。 查询颜色段数可以用线段树维护区间颜色段数。 这道题涉及到区间合并，所以在线段树和lca的时候需要多记录一些东西，当前区间的最左边的颜色，最右边的颜色，已经求出的区间
Codeforces 1253 F. Cheap Robot —— 想法，dijkstra+kruskal重构树+并查集+树链剖分+lca，有丶东西
This way 题意： 给你一张大小为n的图，并且点1~k是充电站。有q个询问，每次询问你从a走到b最少需要的电池大小为多少。 假设你当前电量为c，当走过一个权值为w的边时，你的点会变成c-w，如果这个点是充电站，那么你的电量会便会变回电池容量。 问你你每次需要的电池容量最小是多少。 题解： 有一说一，这道题很厉害。 首先先用dijkstra找到每个点距离它最近的充电站的距离，然后的话
牛客国庆集训派对Day4H 树链博弈
题目：点击打开链接 题意：开始题意没弄明白，必须选一个节点变白，然后再选择祖先或者重新选择其他一个节点变白。 分析：结论是如果树的所有层的黑点的个数是偶数，则先手必败。因为全是偶数，先手造作第k层的点后，那么k层的点就变为奇数了（留给后手一个必胜的状态），这时后手也操作k层的一个点，然后复制先手的操作，一定可以留给先手一个全是偶数的状态。这样，一定是后手走完最后一步，先手必败。 代码： #
Loj#139 树链剖分
题目链接 问题分析 一道比较标准的模板题。唯一需要考虑的是换根操作。 发现换根对链上的操作并没有影响，考虑对树上以\(u\)为根子树的影响。设原树上以\(u\)为根的子树是\(T\)。如果新的根在\(T\)的外部，那么以\(u\)为根的子树不变。如果新根就是\(u\)，那么子树就是整棵树。否则，取原树中\(u\)的一个儿子\(v\)，\(v\)包含新的根，那么新的以\(u\)为根的子树就是整棵树
BZOJ 3631 [JLOI2014]松鼠的新家 树链剖分
Description 松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在“树”上。松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a1，再去a2，……，最后到an，去参观新家。 可是这样会导致维尼重复走很多房间，懒惰的维尼不听地推辞。可是松