树形动规 - Page 4

「CF486D」Valid Sets
Asyouknow,anundirectedconnectedgraphwithnnodesandn - 1edgesiscalledatree.Youaregivenanintegerdandatreeconsistingofnnodes.Eachnodeihasavalueaiassociatedwithit.WecallasetSoftreenodesvalidiffollowingconditionsaresatisfied:Sisnon-empty.Sisconnected.Inotherwords,ifnodesuandvareinS,thenallnodeslyingonthesimplepathbetweenuandvshouldalsobepresentedinS..Yourtaskistocountthenumberofvalidsets.S...
02014年11月12日3,518树形动规

「NOIP模拟赛」LazyChild黑OJ
LazyChild开了一家“善良OJ”。但大多数人都不知道，这其实是家黑OJ。亲爱的同学，请不要惊讶，古时候有黑店，现代为什么不能有黑OJ呢？每AC一道题，网站便会自动在电脑上安装一种木马。LazyChild通过窃取信息获取收益（如网游帐号、OI资料、YuanY和TT的照片等等）。作为一名资深黑客，老Z某日突然发现，“善良OJ”上的木马，自己电脑上都没有。这可十分让他过意不去。老Z决定通过多A题，来丰富自己电脑的病...
02014年11月2日3,622树形动规
「NOIP模拟赛」Kth
「题目描述」给定一个N(2<=N<=150000)个节点N－1边的树，每条边有一个长度L（1<=L<=1000000）。现在定义：“路径(u,v)长度”表示顶点u到v之间的最短路径“u的第k远路径”表示从顶点u出发的第k长路径。请编写一个程序，计算这棵树中每个顶点的的第k远路径的长度。「输入格式」输入第一行包含一个整数T（T<=50），表示测试数据的组数。在每一组测试数据中，第一行为两个整数N和K(1<=K<=20且K<=N...
02014年10月30日3,807树形动规
「hdu2196」Computer
ProblemDescriptionAschoolboughtthefirstcomputersometimeago(sothiscomputer'sidis1).DuringtherecentyearstheschoolboughtN-1newcomputers.Eachnewcomputerwasconnectedtooneofsettledearlier.ManagersofschoolareanxiousaboutslowfunctioningofthenetandwanttoknowthemaximumdistanceSiforwhichi-thcomputerneedstosendsignal(i.e.lengthofcabletothemostdistantcomputer).Youneedtoprovidethisinformation.Hint:the...
02014年10月30日3,923树形动规
「NOIP模拟赛」宠物之战
「问题描述」众所周知，moreD的宠物已经被moreD奴役得体无完肤。这只宠物实在忍无可忍，把自己每天走魔法树的经历告诉了自己的宠物。同时他还说明了自己爬树是多么地慢，以至于moreD每天都残酷地训练他爬树。幸运的是moreD的宠物的宠物不是moreD的宠物，moreD的宠物深知”宠物是用来宠的而不是用来奴役的”这一点，所以moreD的宠物对待自己的宠物很有爱。所以moreD的宠物与其宠物商量着要推翻moreD的暴政，方法是把moreD...
02014年10月29日2,654树形动规
「NOIP模拟赛」警察叔叔就是这个人！
题目背景十个地方十人十色全部都是猥琐大叔这里也是那里也是行踪可疑现如今hentai横行，警察叔叔们不得不采取特♂殊手段惩戒这些家伙题目描述魅力之都是一个有N个路口，M条双向道路连接的城市。警察叔叔绘制了一张特殊的地图，在地图上只保留了N-1条道路，我们称这些道路为「特殊道路」，要保证任意两个路口间有且仅有一条路径，且满足所有保留的道路长度之和最小。现在要在其中一个连接有多条「特殊道路」的路口设立「根据地」...
02014年10月18日3,548树形动规
「BZOJ1131」[POI2008] Sta
Description给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大Input给出一个数字N,代表有N个点.N<=1000000下面N-1条边.Output输出你所找到的点,如果具有多个解,请输出编号最小的那个.SampleInput814564567682434SampleOutput7题解发现从根从某个位置移到它的一个子树得出ans只要O1的时间那么树形dp即可[crayon-6744124e2618a295528228/] ...
02014年10月11日3,504树形动规
「NOIP模拟赛」交通
黄金大神国的首都位于hzwer河中的一座岛屿。一道上班的时候，成千上万辆汽车通过岛屿从西岸的住宅区（由桥连接岛的西部）到东岸的工业区（由桥连接岛的东部）。该岛类似于矩形，它的边平行于主方向。故可将它看作是笛卡尔坐标系中的一个A*B的矩形，它的对角分别为（0,0）和（A,B）。岛上有n个交通节点（后宫建筑），编号为1…n，第i个节点坐标为(xi,yi)。如果一个节点的坐标为(0,y)，它就位于岛的西岸。类似的，坐标为(A,y)的...
02014年9月27日3,735树形动规,图的连通
「BZOJ3631」[JLOI2014] 松鼠的新家
Description松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在“树”上。松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a1，再去a2，……，最后到an，去参观新家。可是这样会导致维尼重复走很多房间，懒惰的维尼不听地推辞。可是松鼠告诉他，每走到一个房间，他就可以...
22014年9月25日5,256深度搜索,树形动规
「CF467D」Fedor and Essay
AfteryouhadhelpedFedortofindfriendsinthe«CallofSoldiers3»game,hestoppedstudyingcompletely.Today,theEnglishteachertoldhimtoprepareanessay.Fedordidn'twanttopreparetheessay,soheaskedAlexforhelp.AlexcametohelpandwrotetheessayforFedor.ButFedordidn'tliketheessayatall.NowFedorisgoingtochangetheessayusingthesynonymdictionaryoftheEnglishlanguage.Fedordoesnotwanttochangethemeaningoftheessa...
02014年9月19日3,270树形动规,图的连通
「CF461B」Appleman and Tree
Applemanhasatreewith n vertices.Someofthevertices(atleastone)arecoloredblackandotherverticesarecoloredwhite.Considerasetconsistingof k (0 ≤ k < n) edgesofAppleman'stree.IfApplemandeletestheseedgesfromthetree,thenitwillsplitinto (k + 1) parts.Note,thateachpartwillbeatreewithcoloredvertices.NowApplemanwonders,whatisthenumberofsetssplittingthetreeinsuchawaythateachresultingp...
02014年8月27日4,528树形动规
「BZOJ1864」[ZJOI2006] 三色二叉树
DescriptionInput仅有一行，不超过500000个字符，表示一个二叉树序列。Output输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。SampleInput1122002010SampleOutput52题解随便dp一下即可f[i][0/1]表示i结点为绿/非绿色的绿色结点的最大个数转移f[x][1]=f[l[x]][0]+f[r[x]][0]+1;f[x][0]=max(f[l[x]][0]+f[r[x]][1],f[r[x]][0]+f[l[x]][1]);最小值类似[crayon-6744124e27975757649113/] &n...
12014年8月1日4,139树形动规