• 【bzoj1180】[CROATIAN2009]OTOCI

    【bzoj1180】[CROATIAN2009]OTOCI

    Description给出n个结点以及每个点初始时对应的权值wi。起始时点与点之间没有连边。有3类操作:1、bridgeAB:询问结点A与结点B是否连通。如果是则输出“no”。否则输出“yes”,并且在结点A和结点B之间连一条无向边。2、penguinsAX:将结点A对应的权值wA修改为X。3、excursionAB:如果结点A和结点B不连通,则输出“impossible”。否则输出结点A到结点B的路径上的点对应的权值的和。给出q个操作,要求在线处理所有...

    62015年7月1日1,971link cut tree
  • 【bzoj2157】旅游

    【bzoj2157】旅游

    DescriptionRay乐忠于旅游,这次他来到了T城。T城是一个水上城市,一共有N个景点,有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本,T城的任意两个景点之间有且只有一条路径。换句话说,T城中只有N−1座桥。Ray发现,有些桥上可以看到美丽的景色,让人心情愉悦,但有些桥狭窄泥泞,令人烦躁。于是,他给每座桥定义一个愉悦度w,也就是说,Ray经过这座桥会增加w的愉悦度,这或许是正的也可能是负的...

    62015年2月15日2,086link cut tree
  • 【hdu5002】Tree

    【hdu5002】Tree

    ProblemDescriptionYouaregivenatreewithNnodeswhicharenumberedbyintegers1..N.Eachnodeisassociatedwithanintegerastheweight.YourtaskistodealwithMoperationsof4types:1.Deleteanedge(x,y)fromthetree,andthenaddanewedge(a,b).Weensurethatitstillconstitutesatreeafteraddingthenewedge.2.Giventwonodesaandbinthetree,changetheweightsofallthenodesonthepathconnectingnodeaandb(includingnodeaandb)toaparticu...

    02014年12月13日1,422link cut tree
  • 【hdu4010】Query on The Trees

    【hdu4010】Query on The Trees

    ProblemDescriptionWehavemetsomanyproblemsonthetree,sotodaywewillhaveaqueryproblemonasetoftrees.ThereareNnodes,eachnodewillhaveauniqueweightWi.Wewillhavefourkindsofoperationsonitandyoushouldsolvethemefficiently.Wishyouhavefun! InputTherearemultipletestcasesinourdataset.Foreachcase,thefirstlinecontainsonlyoneintegerN.(1≤N≤300000)ThenextN‐1lineseachcontainstwointegersx,ywhichme...

    172014年12月11日1,864link cut tree
  • 【bzoj2555】SubString

    【bzoj2555】SubString

    Description懒得写背景了,给你一个字符串init,要求你支持两个操作(1):在当前字符串的后面插入一个字符串(2):询问字符串s在当前字符串中出现了几次?(作为连续子串)你必须在线支持这些操作。Input    第一行一个数Q表示操作个数第二行一个字符串表示初始字符串init接下来Q行,每行2个字符串Type,StrType是ADD的话表示在后面插入字符串。Type是QUERY的话表示询问某字符串在当前字符串中出现了几次。为了体现在...

    02014年9月25日3,462后缀自动机,link cut tree
  • 【bzoj3282】Tree

    【bzoj3282】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上的权值变...

    22014年9月18日2,412link cut tree
  • 【bzoj3514】Codechef MARCH14 GERALD07加强版

    【bzoj3514】Codechef MARCH14 GERALD07加强版

    DescriptionN个点M条边的无向图,询问保留图中编号在[l,r]的边的时候图中的联通块个数。Input第一行四个整数N、M、K、type,代表点数、边数、询问数以及询问是否加密。接下来M行,代表图中的每条边。接下来K行,每行两个整数L、R代表一组询问。对于type=0的测试点,读入的L和R即为询问的L、R;对于type=1的测试点,每组询问的L、R应为Lxorlastans和Rxorlastans。Output K行每行一个整数代表该组询问的联通块...

    32014年9月11日2,954主席树,link cut tree
  • 【bzoj2594】[Wc2006]水管局长数据加强版

    【bzoj2594】[Wc2006]水管局长数据加强版

    DescriptionSC省MY市有着庞大的地下水管网络,嘟嘟是MY市的水管局长(就是管水管的啦),嘟嘟作为水管局长的工作就是:每天供水公司可能要将一定量的水从x处送往y处,嘟嘟需要为供水公司找到一条从A至B的水管的路径,接着通过信息化的控制中心通知路径上的水管进入准备送水状态,等到路径上每一条水管都准备好了,供水公司就可以开始送水了。嘟嘟一次只能处理一项送水任务,等到当前的送水任务完成了,才能处理下一项。在...

    52014年8月13日3,173kruskal,离线处理,link cut tree
  • NOI2014魔法森林

    NOI2014魔法森林

    Description为了得到书法大家的真传,小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图,节点标号为1..N,边标号为1..M。初始时小E同学在号节点1,隐士则住在号节点N。小E需要通过这一片魔法森林,才能够拜访到隐士。魔法森林中居住了一些妖怪。每当有人经过一条边的时候,这条边上的妖怪就会对其发起攻击。幸运的是,在号节点住着两种守护精灵:A型守护精灵与B型守护精灵。...

    82014年8月12日5,711kruskal,link cut tree
  • 【bzoj2631】tree

    【bzoj2631】tree

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

    112014年8月8日2,896link cut tree
  • 【bzoj2002】[Hnoi2010]Bounce 弹飞绵羊

    【bzoj2002】[Hnoi2010]Bounce 弹飞绵羊

    Description某天,Lostmonkey发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。游戏一开始,Lostmonkey在地上沿着一条直线摆上n个装置,每个装置设定初始弹力系数ki,当绵羊达到第i个装置时,它会往后弹ki步,达到第i+ki个装置,若不存在第i+ki个装置,则绵羊被弹飞。绵羊想知道当它从第i个装置起步时,被弹几次后会被弹飞。为了使得游戏更有趣,Lostmonkey可以修改某个弹力装置的弹力系数,任...

    92014年7月30日4,310分块,link cut tree
  • 【bzoj2049】[Sdoi2008]Cave 洞穴勘测

    【bzoj2049】[Sdoi2008]Cave 洞穴勘测

    Description辉辉热衷于洞穴勘测。某天,他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测,辉辉发现这片区域由n个洞穴(分别编号为1到n)以及若干通道组成,并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来,那么这两个洞穴就是连通的,按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。洞穴都十分坚固无法破坏,然而通道不太稳定,时常因为外界影响而发...

    322014年7月30日3,426link cut tree
  • 【bzoj1036】[ZJOI2008]树的统计Count

    【bzoj1036】[ZJOI2008]树的统计Count

    Description一棵树上有n个节点,编号分别为1到n,每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作:I.CHANGEut:把结点u的权值改为tII.QMAXuv:询问从点u到点v的路径上的节点的最大权值III.QSUMuv:询问从点u到点v的路径上的节点的权值和注意:从点u到点v的路径上的节点包括u和v本身Input输入的第一行为一个整数n,表示节点的个数。接下来n–1行,每行2个整数a和b,表示节点a和节点b之...

    252014年4月6日6,477线段树,树链剖分,link cut tree