dfs序 - hzwer.com

「BZOJ3991」[SDOI2015] 寻宝游戏
Description 小B最近正在玩一个寻宝游戏，这个游戏的地图中有N个村庄和N-1条道路，并且任何两个村庄之间有且仅有一条路径可达。游戏开始时，玩家可以任意选择一个村庄，瞬间转移到这个村庄，然后可以任意在地图的道路上行走，若走到某个村庄中有宝物，则视为找到该村庄内的宝物，直到找到所有宝物并返回到最初转移到的村庄为止。小B希望评测一下这个游戏的难度，因此他需要知道玩家找到所有宝物需要行走的最短路程。但是这个...
82015年4月17日8,870虚树,dfs序,STL,最近公共祖先

「fjWC2015」当小威遇上经济危机
格式问题比较大题面就不贴了tex搞的pdf太酷炫大意给定一棵树，支持修改点权，询问某个点子树内最大值是否超过根[crayon-662f69a5ceaeb088163457/]
52015年2月4日4,044dfs序,线段树
「BZOJ3772」精神污染
Description兵库县位于日本列岛的中央位置，北临日本海，南面濑户内海直通太平洋，中央部位是森林和山地，与拥有关西机场的大阪府比邻而居，是关西地区面积最大的县，是集经济和文化于一体的一大地区，是日本西部门户，海陆空交通设施发达。濑户内海沿岸气候温暖，多晴天，有日本少见的贸易良港神户港所在的神户市和曾是豪族城邑“城下町”的姬路市等大城市，还有以疗养地而闻名的六甲山地等。兵库县官方也大力发展旅游，为了方便...
02015年1月27日6,031dfs序,主席树
「BZOJ3611」[HEOI2014] 大工程
题面和题解见http://www.cnblogs.com/zyfzyf/p/4231356.html[crayon-662f69a5cf9ce553106161/]
22015年1月20日6,164dfs序,虚树,树形动规,最近公共祖先
「BZOJ3306」树
Description给定一棵大小为n的有根点权树,支持以下操作:•换根•修改点权•查询子树最小值Input第一行两个整数n,Q,分别表示树的大小和操作数。接下来n行,每行两个整数f,v,第i+1行的两个数表示点i的父亲和点i的权。保证f<i。如果f=0,那么i为根。输入数据保证只有i=1时,f=0。接下来m行,为以下格式中的一种:•Vxy表示把点x的权改为y•Ex表示把有根树的根改为点x•Qx表示查询点x的子树最小值Output对于每个Q,输出子树最小值...
02014年12月11日7,109dfs序,线段树,树上倍增
「BZOJ2819」Nim
Description著名游戏设计师vfleaking，最近迷上了Nim。普通的Nim游戏为：两个人进行游戏，N堆石子，每回合可以取其中某一堆的任意多个，可以取完，但不可以不取。谁不能取谁输。这个游戏是有必胜策略的。于是vfleaking决定写一个玩Nim游戏的平台来坑玩家。为了设计漂亮一点的初始局面，vfleaking用以下方式来找灵感：拿出很多石子，把它们聚成一堆一堆的，对每一堆编号1,2,3,4,...n,在堆与堆间连边，没有自环与重边，从任意堆...
82014年12月9日7,034dfs序,树状数组,博弈论
「BZOJ3653」谈笑风生
Description设T为一棵有根树，我们做如下的定义：•设a和b为T中的两个不同节点。如果a是b的祖先，那么称“a比b不知道高明到哪里去了”。•设a和b为T中的两个不同节点。如果a与b在树上的距离不超过某个给定常数x，那么称“a与b谈笑风生”。给定一棵n个节点的有根树T，节点的编号为1到n，根节点为1号节点。你需要回答q个询问，询问给定两个整数p和k，问有多少个有序三元组(a;b;c)满足：1.a、b和c为T中三个不同的点，且a为p号节...
02014年12月8日6,799dfs序,线段树
NOI2011阿狸的打字机
Description 阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和'B'、'P'两个字母。经阿狸研究发现，这个打字机是这样工作的：l输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。l按一下印有'B'的按键，打字机凹槽中最后一个字母会消失。l按一下印有'P'的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消...
32014年12月6日9,744dfs序,AC自动机,树状数组
「POJ3321」Apple Tree
DescriptionThereisanappletreeoutsideofkaka'shouse.Everyautumn,alotofappleswillgrowinthetree.Kakalikesappleverymuch,sohehasbeencarefullynurturingthebigappletree.ThetreehasNforkswhichareconnectedbybranches.Kakanumberstheforksby1toNandtherootisalwaysnumberedby1.Appleswillgrowontheforksandtwoapplewon'tgrowonthesamefork.kakawantstoknowhowmanyapplesarethereinasub-tree,forhisstudyoftheproduceabi...
02014年8月1日6,468dfs序,线段树
「BZOJ1103」[POI2007] 大都市meg
Description在经济全球化浪潮的影响下,习惯于漫步在清晨的乡间小路的邮递员BlueMary也开始骑着摩托车传递邮件了。不过，她经常回忆起以前在乡间漫步的情景。昔日，乡下有依次编号为1..n的n个小村庄，某些村庄之间有一些双向的土路。从每个村庄都恰好有一条路径到达村庄1（即比特堡）。并且，对于每个村庄，它到比特堡的路径恰好只经过编号比它的编号小的村庄。另外，对于所有道路而言，它们都不在除村庄以外的其他地点相遇。在这...
22014年6月15日7,156dfs序,树状数组