树链专题
树链剖分 + 后缀数组 - E. Misha and LCP on Tree
E. Misha and LCP on Tree Problem's Link Mean: 给出一棵树，每个结点上有一个字母。每个询问给出两个路径，问这两个路径的串的最长公共前缀。 analyse: 做法：树链剖分+后缀数组. 记录每条链的串，正反都需要标记，组成一个长串. 然后记录每条链对应的串在大串中的位置,对大串求后缀数组,最后询问就是在一些链
【HDU】5029 Relief grain 树链剖分+离线标记法
传送门：【HDU】5029 Relief grain 题目分析：这题的方法太美妙了！ 首先看到这是一颗树，那么很容易想到树链剖分。然后想到可以将查询排个序，然后每一种查询执行完以后更新每个点的最优值。但是这样进行的复杂度太高！尤其是当z给的没有一样的时候尤其如此。 那么我们是否可以找到更加高效的算法？ 答案是肯定的！ 先简化一下问题，如果这些操作是在线段上进行的，我们怎么求解？
【HDU】5221 Occupation【树链剖分】
传送门：【HDU】5221 Occupation 题目分析： 最直接的想法，用一棵树链剖分维护路径，一棵dfs序线段树维护子树。因为每次最多修改一个点，所以修改的时候我们暴力修改每个点就可以了。 my code: my~~code: #pragma comment(linker, "/STACK:102400000,102400000")#include <stdio.h>#in
【HDU】5436 Transmigration tree【树链剖分+dp+rmq】
题目链接：【HDU】5436 Transmigration tree #pragma comment(linker, "/STACK:16777216")#include <stdio.h>#include <string.h>#include <vector>#include <algorithm>using namespace std ;typedef long long LL ;
【HDU】5566 Clarke and room【树链剖分+AC自动机】
题目链接：Clarke and room #include <bits/stdc++.h>using namespace std ;typedef long long LL ;#define ls ( o << 1 )#define lson ls , l , m#define rs ( o << 1 | 1 )#define rson rs , m + 1 , r#define rt
hdu5052 Yaoge’s maximum profit 树链剖分
一棵树上，从u走到v，在某点买入，咋之后的某点卖出，求最大利润。 维护正着走和反着走的最大利润。 #include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstring>#include<vector>#include<set>#include<map>#include<que
poj3237--Tree(树链剖分+线段树)
题目链接：poj--3237 题意很简单，给出n个节点的一棵树，有三种操作： 1、C修改第i条边的值为v 2、N改变节点a到b内边的权值的符号（取反） 3、Q询问节点a到b内权值的最大值 首先树链剖分，将边整合到线段树上，线段树数组cl，因为存在取反操作，所以最大值可能是由最小值取反得到，所以记录最大和最小值，cl[i][0]记录第i段的最大值，cl[i][1]记录最小值，lazy做标记
BZOJ 3531 旅行【树链剖分】
[Sdoi2014] 简单的树链剖分 以每个信仰应该建一个线段树，空间复杂度为 O(5×1010) O(5\times 10^{10}) 因此会爆空间，所以需要动态申请空间。 // whn6325689// Mr.Phoebe// http://blog.csdn.net/u013007900#include <algorithm>#include <
Aoj 2450 Do use segment tree【树链剖分】
树链剖分，个人因为姿势太丑就不发代码了。 维护四个域。 区间和，右端最大连续值，左端最大连续值，答案。 注意的是，2操作是一个有序的操作，因此需要求一个LCA，从某点更新到LCA，再从LCA更新到另一个点。当然也有不要LCA的方法，就是通过判断深度，不swap，直接旋转地找。 // whn6325689// Mr.Phoebe// http://blog.
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 （树链剖分+线段树）
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