link cut tree - hzwer.com

「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日6,074link cut tree

「BZOJ2157」旅游
DescriptionRay乐忠于旅游，这次他来到了T城。T城是一个水上城市，一共有N个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T城的任意两个景点之间有且只有一条路径。换句话说，T城中只有N−1座桥。Ray发现，有些桥上可以看到美丽的景色，让人心情愉悦，但有些桥狭窄泥泞，令人烦躁。于是，他给每座桥定义一个愉悦度w，也就是说，Ray经过这座桥会增加w的愉悦度，这或许是正的也可能是负的...
62015年2月15日4,983link cut tree
「hdu5002」Tree
ProblemDescriptionYouaregivenatreewithNnodeswhicharenumberedbyintegers1..N.Eachnodeisassociatedwithanintegerastheweight.YourtaskistodealwithMoperationsof4types:1.Deleteanedge(x,y)fromthetree,andthenaddanewedge(a,b).Weensurethatitstillconstitutesatreeafteraddingthenewedge.2.Giventwonodesaandbinthetree,changetheweightsofallthenodesonthepathconnectingnodeaandb(includingnodeaandb)toaparticu...
02014年12月13日4,012link cut tree
「hdu4010」Query on The Trees
ProblemDescriptionWehavemetsomanyproblemsonthetree,sotodaywewillhaveaqueryproblemonasetoftrees.ThereareNnodes,eachnodewillhaveauniqueweightWi.Wewillhavefourkindsofoperationsonitandyoushouldsolvethemefficiently.Wishyouhavefun! InputTherearemultipletestcasesinourdataset.Foreachcase,thefirstlinecontainsonlyoneintegerN.(1≤N≤300000)ThenextN‐1lineseachcontainstwointegersx,ywhichme...
172014年12月11日5,375link cut tree
「BZOJ2555」SubString
Description懒得写背景了，给你一个字符串init，要求你支持两个操作(1):在当前字符串的后面插入一个字符串(2):询问字符串s在当前字符串中出现了几次？(作为连续子串)你必须在线支持这些操作。Input 第一行一个数Q表示操作个数第二行一个字符串表示初始字符串init接下来Q行，每行2个字符串Type,StrType是ADD的话表示在后面插入字符串。Type是QUERY的话表示询问某字符串在当前字符串中出现了几次。为了体现在...
02014年9月25日8,821后缀自动机,link cut tree
「BZOJ3282」Tree
Description给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的。１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到Ｙ已经联通则无需连接。２：后接两个整数（ｘ，ｙ），代表删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。３：后接两个整数（ｘ，ｙ），代表将点Ｘ上的权值变...
22014年9月18日5,750link cut tree
「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日7,920主席树,link cut tree
「BZOJ2594」[Wc2006] 水管局长数据加强版
DescriptionSC省MY市有着庞大的地下水管网络，嘟嘟是MY市的水管局长（就是管水管的啦），嘟嘟作为水管局长的工作就是：每天供水公司可能要将一定量的水从x处送往y处，嘟嘟需要为供水公司找到一条从A至B的水管的路径，接着通过信息化的控制中心通知路径上的水管进入准备送水状态，等到路径上每一条水管都准备好了，供水公司就可以开始送水了。嘟嘟一次只能处理一项送水任务，等到当前的送水任务完成了，才能处理下一项。在...
52014年8月13日7,972kruskal,离线处理,link cut tree
NOI2014魔法森林
Description为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图，节点标号为1..N，边标号为1..M。初始时小E同学在号节点1，隐士则住在号节点N。小E需要通过这一片魔法森林，才能够拜访到隐士。魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻击。幸运的是，在号节点住着两种守护精灵：A型守护精灵与B型守护精灵。...
82014年8月12日23,907kruskal,link cut 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日8,020link cut tree
「BZOJ2002」[HNOI2010] Bounce 弹飞绵羊
Description某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任...
102014年7月30日16,338分块,link cut tree
「BZOJ2049」[SDOI2008] Cave 洞穴勘测
Description辉辉热衷于洞穴勘测。某天，他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测，辉辉发现这片区域由n个洞穴（分别编号为1到n）以及若干通道组成，并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来，那么这两个洞穴就是连通的，按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。洞穴都十分坚固无法破坏，然而通道不太稳定，时常因为外界影响而发...
322014年7月30日9,054link cut tree