【bzoj 十连测】[noip2016十连测第二场]Problem C. Dash Speed（树链剖分+并查集）
【题解】【树链剖分+并查集+二分】 【线段树维护边的信息，类似next数组的存储。并查集维护父子信息和每个区间的起点终点。考虑每次限定一个速度范围，速度在这个范围内的边都可以操作。分治，每次做完一个区间再把当前不符合的递归到下一区间处理，由于存在回溯和分治两侧，所以这里并查集不能进行路径压缩。...
树剖+线段树||树链剖分||BZOJ2238||Mst
题面：https://www.lydsy.com/JudgeOnline/problem.php?id=2238思路：先求个最小生成树，然后就对最小生成树上的边做树剖，依次对非树边进行处理，维护非树边两端连成的路径的最小值（用非树边的权值维护），然后对于每个询问，求出覆盖在那条线段上的最小值，用re...
hdu3966 树链剖分+成段更新
给你n个点，m条边，p次操作。n个点相连后是一棵树。每次操作可以是x 到 y 增加 z，或者减z，或者问当前点的值是多少。可以将树分成链，每个点在线段树上都有自己的点，然后线段树成段更新一下。#pragma comment(linker, "/STACK:1024000000,1024000000"...
FZU 2082 过路费 (树链剖分 修改单边权)
题目链接：http://acm.fzu.edu.cn/problem.php?pid=2082树链剖分模版题，求和，修改单边权。 #include <iostream> #include <cstdio> #include <algorithm> #include...
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除以路径上所有边乘积，即；对于第二种操作，就是线段树上的单点更新。因为给的是...
数链剖分（Aragorn's Story ）
题目链接：https://vjudge.net/contest/279350#problem/A题目大意：n个点，m条边，然后q次询问，因为在树上，两个点能确定一条直线，我们可以对这条直线上的所有值进行加减操作，也可以单点询问。各个数组的作用：sto是刚开始的输入数据，head是前向星，dfsnum...
SPOJ QTREE-Query on a tree-树链剖分-边权
用每个点代表父节点到此点的边。建立一一映射后就可以用点权的方法处理了。注意的是路径两端节点的处理 #include <cstdio> #include <algorithm> #include <vector> using namespace std; const...
BZOJ 4034: [HAOI2015]T2( 树链剖分 )
树链剖分...子树的树链剖分序必定是一段区间 , 先记录一下就好了---------------------------------------------------------------------------#include<cstdio>#include<cstring&...
[JSOI2016]轻重路径[树链剖分]
题意题目链接分析先对原树树剖，在一次删点操作后从根节点开始二分，如果一条边从重边变成轻边，必然有 \(size_u\le \frac{1}{2}size_{rt}\) (取等号是特判对应儿子消失)，二分后，将这个位置作为顶端递归寻找。容易发现这样操作的次数 \(< logn\) 次。判定一条边...
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$数组右移一格，还需要同时加上一个值。显然用线段树等数据结构额外维护是不现实的，我们...
【BZOJ3626】LCA（树链剖分，Link-Cut Tree）
【BZOJ3626】LCA（树链剖分，Link-Cut Tree）题面Description给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。有q次询问，每次询问给出l r z，...
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题意：给你一棵树，每个节点有一个值，然后任给树上的两点，问这两点的最长连续递增区间是多少题解：先树链剖分，然后结合线段树的区间合并来搞，注意的是要记录递增和递减两个状态，因为线段树的区间都是从根到子...