树形动规 - Page 3

「BZOJ2815」[ZJOI2012] 灾难
小强和阿米巴0.0fhq神犇的题==http://fanhq666.blog.163.com/blog/static/8194342620124274154996/[crayon-6767f38dcfc33642368931/]
22015年2月5日6,987树形动规,拓扑排序,最近公共祖先

「BZOJ3162」独钓寒江雪
Description题解参照2007杨弋论文vfk的博客http://vfleaking.blog.163.com/blog/static/17480763420134452440444/太神了orzorzorz[crayon-6767f38dd02e1318320088/]
72015年1月28日4,802树形动规,哈希表
「BZOJ3611」[HEOI2014] 大工程
题面和题解见http://www.cnblogs.com/zyfzyf/p/4231356.html[crayon-6767f38dd0b89888638050/]
22015年1月20日6,446虚树,dfs序,树形动规,最近公共祖先
「BZOJ2286」[SDOI2011] 消耗战
Description在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总...
22015年1月20日8,343虚树,树形动规
「BZOJ3696」「FJ2014集训」化合物
Description 首长NOI惨跪，于是去念文化课了。现在，他面对一道化学题。这题的来源是因为在一个奇怪的学校两个化竞党在玩一个奇怪的博弈论游戏。这个游戏很蛋疼，我相信你们也没有兴趣听。由于这个游戏涉及博弈论，因此化竞的同学就要求首长求一个类似SG函数的值。他们手中有一种非常神奇的化合物，它的分子由N个原子组成（不要在意一个原子可能和及其多个原子成键这个细节）。这个分子构成一个树结构，1号分子为根。 ...
02015年1月4日4,487树形动规,最近公共祖先
「CF500D」New Year Santa Network
NewYeariscominginTreeWorld!Inthisworld,asthenameimplies,therearencitiesconnectedbyn - 1roads,andforanytwodistinctcitiestherealwaysexistsapathbetweenthem.Thecitiesarenumberedbyintegersfrom1ton,andtheroadsarenumberedbyintegersfrom1ton - 1.Let'sdefined(u, v)astotallengthofroadsonthepathbetweencityuandcityv.Asanannualevent,peopleinTreeWorldrepairsexactlyoneroadperyear.Asaresult,theleng...
02015年1月4日3,728树形动规,排列组合
「泉七培训 – 杨国烨」出纳员zgg
「题目描述」zgg去当出纳员了！zgg所在的公司的工资是按年发放的。在每年的元旦，每个员工的工资额会被修改为0元；在每年的除夕，员工按工资额领取相应的工资。zgg的上司是一位和蔼可亲的老爷爷，他经常给员工们提升工资。而zgg的工作，就是帮助所有员工统计最后的工资额。老爷爷只会用以下两种指令给员工们提升工资：1.让某个员工的工资额提升X元；2.让所有员工的工资额变成原来的X倍。然则，由于老爷爷实在是太和蔼了，以至于提...
02014年12月26日3,345树形动规
「BZOJ2427」[HAOI2010] 软件安装
Description现在我们的手头有N个软件，对于一个软件i，它要占用Wi的磁盘空间，它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大（即Vi的和最大）。但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够...
42014年12月13日6,586树形动规,图的连通
NOI2011道路修建
Description在W星球上有n个国家。为了各自国家的经济发展，他们决定在各个国家之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬，他们只愿意修建恰好n–1条双向道路。每条道路的修建都要付出一定的费用，这个费用等于道路长度乘以道路两端的国家个数之差的绝对值。例如，在下图中，虚线所示道路两端分别有2个、4个国家，如果该道路长度为1，则费用为1×|2–4|=2。图中圆圈里的数字表示国家的编号。由于国家的数量十...
02014年12月10日3,159树形动规
「BZOJ1060」[ZJOI2007] 时态同步
Description小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，都存在且仅存在一条通路（通路指连接两个元件的导线序列）。在电路板上存在一个特殊的元件称为“激发器”。当激发器工作后，产生一个激励电流，通过导线传向每一个它所连接的节点。而中间节点接收到激励电流后，得到信...
22014年11月30日4,875树形动规
「BZOJ1017」[JSOI2008] 魔兽地图DotR
DescriptionDotR(DefenseoftheRobots)Allstars是一个风靡全球的魔兽地图，他的规则简单与同样流行的地图DotA(DefenseoftheAncients)Allstars。DotR里面的英雄只有一个属性——力量。他们需要购买装备来提升自己的力量值，每件装备都可以使佩戴它的英雄的力量值提高固定的点数，所以英雄的力量值等于它购买的所有装备的力量值之和。装备分为基本装备和高级装备两种。基本装备可以直接从商店里面用金币购买，而高级装备...
42014年11月23日7,306树形动规
NOIP2014联合权值
题目描述Description无向连通图G有n个点，n-1条边。点从1到n依次编号，编号为i的点的权值为Wi ，每条边的长度均为1。图上两点(u, v)的距离定义为u点到v点的最短距离。对于图G上的点对(u,v)，若它们的距离为2，则它们之间会产生Wu×Wv的联合权值。请问图G上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？输入输出格式Input/output输入格式：输入文件名为link.in。第一行包含1个...
22014年11月22日7,245树形动规