Category Archives: 树链剖分

ACdream 1103 瑶瑶正式成为CEO (树链剖分,费用流)

一颗n个点的有向边树,这个基础上添加了m条有向边,变成一个DAG。每条边都有ai, bi, ci, di,di …

HDU 5111 Alexandra and Two Trees (树链剖分,主席树)

给出两棵树,计算第一棵树链条[u1, v1] 和 第二棵树链条[u2, v2]的顶点颜色交集的大小。保证同一颗 …

2016 ACM/ICPC Asia Regional Shenyang Online

1002 – List wants to travel 给出n个点的树,每条边有一种颜色,两种操作 …

HDU 5458 Stability (双连通缩点,树链剖分)

一个图,可能存在自环或者重边,现在有两个操作:1. 将a-b这条边删除;2. 询问单独删除那些边可以使a和b不 …

HDU 5452 Minimum Cut (树链剖分)

给出一棵树,然后在树上添加m – n + 1条边,形成一个没有自环和重边的图,现在要找一个割边集, …

HDU 5293 Tree chain problem (树形dp,树链剖分维护)

一棵树,给出m个路径,每个路径都有一个权值,求一个方案将这些路径放入树中并且互相没有公共点的一个最大权值和。 …

HDU 4897 Little Devil I (树链剖分,好题)

给出一棵树,开始时树的每条边都是白色,接下来q个操作: 1. 将树链u-v上的边翻转(白色变成黑色,黑色变成白 …

UVA 11354 Bond (瓶颈路,树链剖分)

给出一张图,q个询问,求u到v的所有路径中瓶颈路最小的,瓶颈路:一条路径上的最大值 瓶颈路就是最小生成树的边, …

HDU 5566 Clarke and room (树链剖分,线段树,ac自动机)

给出一棵树,树上每个节点有一个名字字符串,有q个询问,计算树链u-v经过的点对应的字符串是si的子串的最大长度 …

BNUOJ 39566 Do use segment tree (树链剖分,线段树)

求树上u-v之间路径点权的最大连续和,同时有更新操作,将u-v路劲点权全部变成c 树链剖分套个线段树,维护:左 …