Category Archives: 链分治

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

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

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

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

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 树链剖分套个线段树,维护:左 …

HDU 5052 Yaoge’s maximum profit (树链剖分,线段树)

题意:一个人做经商,他要在不同城市买鸡汤或者卖鸡汤,城市之间连成一棵树,现在每次他会从u走到v但是,路径上的鸡 …

HDU 5029 Relief grain (树链剖分,线段树)

题意:一棵树,每次将某个条链染成同种色,问每个点没染次数最多的颜色是什么,如果没有则输出0. 题解:这题想好各 …

HYSBZ 1146 网络管理Network (树链剖分,数状数组套treap)

题意:对于一棵树,每个节点有权值,动态修改权值并且询问某条链第k大的权值是多少。 题解:这题首先要用树链剖分将 …

HYSBZ 1036 树的统计Count (树链剖分)

在一颗树上操作,三种操作,将树某个点权改变,询问数某天链的最大值和点权和.裸的树剖. [crayon-5c0f …