HDU 3966 Aragorn's Story 动态树 树链剖分
Aragorn's StoryTime Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) 【Problem Description】Our protagonist is the handso...
树链剖分+线段树 CF 593D Happy Tree Party（快乐树聚会）
题目链接题意：有n个点的一棵树，两种操作：1. a到b的路径上，给一个y，对于路径上每一条边，进行操作，问最后的y；2. 修改某个条边p的值为c思路：链上操作的问题，想树链剖分和LCT，对于第一种操作，因为是向下取整，考虑y除以路径上所有边乘积，即；对于第二种操作，就是线段树上的单点更新。因为给的是...
SPOJ QTREE-Query on a tree-树链剖分-边权
用每个点代表父节点到此点的边。建立一一映射后就可以用点权的方法处理了。注意的是路径两端节点的处理 #include <cstdio> #include <algorithm> #include <vector> using namespace std; const...
BZOJ 4034: [HAOI2015]T2( 树链剖分 )
树链剖分...子树的树链剖分序必定是一段区间 , 先记录一下就好了---------------------------------------------------------------------------#include<cstdio>#include<cstring&...
hdu_4897_Little Devil I(树链剖分)
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4897题意：有三种操作，1是在树上的两个节点之间的路径改变当前的颜色，2是改变树上有且只有一个端点在u,v之间的边的颜色，3是询问u,v之间黑色边的条数题解：对于1，就是一般的树链剖分操作，对于2，我们知...
BZOJ 1984: 月下“毛景树” [树链剖分 边权]
1984: 月下“毛景树”Time Limit: 20 Sec Memory Limit: 64 MBSubmit: 1728 Solved: 531[Submit][Status][Discuss]Description毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。 毛毛虫经过千山万...
BZOJ1758[Wc2010]重建计划——分数规划+长链剖分+线段树+二分答案+树形DP
题目描述输入第一行包含一个正整数N，表示X国的城市个数. 第二行包含两个正整数L和U，表示政策要求的第一期重建方案中修建道路数的上下限 接下来的N-1行描述重建小组的原有方案，每行三个正整数Ai,Bi,Vi分别表示道路(Ai,Bi),其价值为Vi 其中城市由1..N进行标号输出输出最大平均估值，保留...
bzoj2243树链剖分+区间合并
树链上区间合并的问题比区间修改要复杂，因为每一条重链在线段树上分布一般都是不连续的，所以在进行链上操作时要手动将其合并起来，维护两个端点值处理时的方向问题：lca->u是一个方向，lca->v是另一个方向，到最后合并这两个放向时都看左端点即可#include<cstring>...
codevs 1228 苹果树 树链剖分讲解
题目：codevs 1228 苹果树链接：http://codevs.cn/problem/1228/看了这么多树链剖分的解释，几个小时后总算把树链剖分弄懂了。树链剖分的功能：快速修改，查询树上的路径。比如一颗树首先，我们要把树剖分成树链。定义：fa[x]是x节点的上一层节点（就是他的爸爸）。dee...
BZOJ4712洪水——动态DP+树链剖分+线段树
题目描述小A走到一个山脚下，准备给自己造一个小屋。这时候，小A的朋友（op，又叫管理员）打开了创造模式，然后飞到山顶放了格水。于是小A面前出现了一个瀑布。作为平民的小A只好老实巴交地爬山堵水。那么问题来了：我们把这个瀑布看成是一个n个节点的树，每个节点有权值（爬上去的代价）。小A要选择一些节点，以其...
Luogu2993 FJOI2014 最短路径树问题 最短路树、长链剖分
传送门强行二合一最为致命第一问直接最短路+$DFS$解决考虑第二问，与深度相关，可以考虑长链剖分。设$f_{i,j}$表示长度为$i$，经过边数为$j$时的最大边权和，考虑到每一次从重儿子转移过来的时候，不仅要将$f$数组右移一格，还需要同时加上一个值。显然用线段树等数据结构额外维护是不现实的，我们...
2018牛客网暑假ACM多校训练赛（第七场）I Tree Subset Diameter 动态规划 长链剖分 线段树
原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round7-I.html题目传送门 - https://www.nowcoder.com/acm/contest/145/I题意给定一棵有 $n$ 个节点的树，问有多少...
hdu_4718_The LCIS on the Tree(树链剖分+线段树合并)
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4718题意：给你一棵树，每个节点有一个值，然后任给树上的两点，问这两点的最长连续递增区间是多少题解：先树链剖分，然后结合线段树的区间合并来搞，注意的是要记录递增和递减两个状态，因为线段树的区间都是从根到子...
【树链剖分】洛谷P3384树剖模板
题目描述如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和操作3： 格式： 3 x z 表示将以x为根...
hdu_5044_Tree(树链剖分)
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=5044题意：给一棵树，在点和边上操作题解：树链剖分，剖完后用树状数组维护即可，因为只有加减操作，连树状的部分都不用写，最后要注意当n等于1的情况 #include<cstdio> #pragm...
BZOJ 1146: [CTSC2008]网络管理Network( 树链剖分 + 树状数组套主席树 )
树链剖分完就成了一道主席树裸题了, 每次树链剖分找出相应区间然后用BIT+(可持久化)权值线段树就可以完成计数. 但是空间问题很严重....在修改时不必要的就不要新建, 直接修改原来的..详见代码. 时间复杂度O(N*log^3(N))--------------------------------...
[HDU 5293]Tree chain problem(树形dp+树链剖分)
[HDU 5293]Tree chain problem(树形dp+树链剖分)题面在一棵树中，给出若干条链和链的权值，求选取不相交的链使得权值和最大。分析考虑树形dp，dp[x]表示以x为子树的最大权值和（选的链都在i的子树中）设sum[x]表示x的儿子的dp值和，即\(\sum _{y \in \...
【树链剖分】【树状数组】【最近公共祖先】【块状树】bzoj3631 [JLOI2014]松鼠的新家
裸题，树状数组区间修改+单点查询。当然要稍微讨论一下链的左右端点是否修改的情况咯。#include<cstdio>#include<algorithm>#include<cmath>using namespace std;#define N 300001int e...
[BZOJ3631][JLOI2014]松鼠的新家（树链剖分）
[BZOJ3631]树剖模板题了，Code#include <cstdio>#include <algorithm>#define MID int mid=(l+r)>>1,ls=id<<1,rs=id<<1|1#define N 3000...
Query on a tree——树链剖分整理
树链剖分整理树链剖分就是把树拆成一系列链，然后用数据结构对链进行维护。通常的剖分方法是轻重链剖分，所谓轻重链就是对于节点u的所有子结点v，size[v]最大的v与u的边是重边，其它边是轻边，其中size[v]是以v为根的子树的节点个数，全部由重边组成的路径是重路径，根据论文上的证明，任意一点到根的路...