分类 动态树 LCT 下的文章

BZOJ 2631: tree

Description一棵n个点的树,每个点的初始权值为1。对于这棵树有q个操作,每个操作为以下四种操作之一:u v c:将u到v的路径上的点的权值都加上自然数c;u1 v1 u2 v2:将树中原有的边(u1,v1)删除,加入一条新边(u2,v2),保证操作完之后仍然是一棵树;u v c:将u到v的路径上的点的权值都乘上自然数c;/ u v:询问u到v的路径上的点的权值和,求出答案对于51061的余数。Input第一行两个整数n,q接下来n-1行每行两个正整数u,v,描述这棵树接下来q行,每行描述一个操作Output对于每个/对应的答案输出一行Sample Input3 2- 阅读剩余部分 -

BZOJ 3282: Tree

Description给定N个点以及每个点的权值,要你处理接下来的M个操作。操作有4种。操作从0到3编号。点从1到N编号。0:后接两个整数(x,y),代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1:后接两个整数(x,y),代表连接x到y,若x到Y已经联通则无需连接。2:后接两个整数(x,y),代表删除边(x,y),不保证边(x,y)存在。3:后接两个整数(x,y),代表将点X上的权值变成Y。Input第1行两个整数,分别为N和M,代表点数和操作数。第2行到第N+1行,每行一个整数,整数在[1,10^9]内,代表每个点的权值。第N+2行到第N+M+1行,- 阅读剩余部分 -

BZOJ 2049: [Sdoi2008]Cave 洞穴勘测

Description辉辉热衷于洞穴勘测。某天,他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测,辉辉发现这片区域由n个洞穴(分别编号为1到n)以及若干通道组成,并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来,那么这两个洞穴就是连通的,按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。洞穴都十分坚固无法破坏,然而通道不太稳定,时常因为外界影响而发生改变,比如,根据有关仪器的监测结果,123号洞穴和127号洞穴之间有时会出现一条通道,有时这条通道又会因为某种稀奇古怪的原因被毁。辉辉有一台监测仪器可以实时将通道的- 阅读剩余部分 -

BZOJ 2002: [Hnoi2010]Bounce 弹飞绵羊 LCT/分块

Description某天,Lostmonkey发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。游戏一开始,Lostmonkey在地上沿着一条直线摆上n个装置,每个装置设定初始弹力系数ki,当绵羊达到第i个装置时,它会往后弹ki步,达到第i+ki个装置,若不存在第i+ki个装置,则绵羊被弹飞。绵羊想知道当它从第i个装置起步时,被弹几次后会被弹飞。为了使得游戏更有趣,Lostmonkey可以修改某个弹力装置的弹力系数,任何时候弹力系数均为正整数。Input第一行包含一个整数n,表示地上有n个装置,装置的编号从0到n-1,接下来一行有n个正整数,依- 阅读剩余部分 -