• 【bzoj3572】[Hnoi2014]世界树

    【bzoj3572】[Hnoi2014]世界树

    Description 世界树是一棵无比巨大的树,它伸出的枝干构成了整个世界。在这里,生存着各种各样的种族和生灵,他们共同信奉着绝对公正公平的女神艾莉森,在他们的信条里,公平是使世界树能够生生不息、持续运转的根本基石。世界树的形态可以用一个数学模型来描述:世界树中有n个种族,种族的编号分别从1到n,分别生活在编号为1到n的聚居地上,种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连,道路的长度为1。保...

    22015年4月21日3,112虚树,树形动规
  • 【bzoj3573】[Hnoi2014]米特运输

    【bzoj3573】[Hnoi2014]米特运输

    Description米特是D星球上一种非常神秘的物质,蕴含着巨大的能量。在以米特为主要能源的D星上,这种米特能源的运输和储存一直是一个大问题。D星上有N个城市,我们将其顺序编号为1到N,1号城市为首都。这N个城市由N-1条单向高速通道连接起来,构成一棵以1号城市(首部)为根的树,高速通道的方向由树中的儿子指向父亲。树按深度分层:根结点深度为0,属于第1层;根结点的子节点深度为1,属于第2层;依此类推,深度为i的结点...

    02015年4月21日1,445树形动规
  • 【bzoj1912】[Apio2010]patrol 巡逻

    【bzoj1912】[Apio2010]patrol 巡逻

    DescriptionInput第一行包含两个整数n,K(1≤K≤2)。接下来n–1行,每行两个整数a,b,表示村庄a与b之间有一条道路(1≤a,b≤n)。Output输出一个整数,表示新建了K条道路后能达到的最小巡逻距离。SampleInput8112313453758556SampleOutput11HINT10%的数据中,n≤1000,K=1;30%的数据中,K=1;80%的数据中,每个村庄相邻的村庄数不超过25;90%的数据中,每个村庄相邻的村庄数不超过150;100%的数据中,3≤n≤100,000,1...

    02015年4月9日1,381树形动规
  • 【bzoj3522】[Poi2014]Hotel

    【bzoj3522】[Poi2014]Hotel

    Description有一个树形结构的宾馆,n个房间,n-1条无向边,每条边的长度相同,任意两个房间可以相互到达。吉丽要给他的三个妹子各开(一个)房(间)。三个妹子住的房间要互不相同(否则要打起来了),为了让吉丽满意,你需要让三个房间两两距离相同。有多少种方案能让吉丽满意?Input第一行一个数n。接下来n-1行,每行两个数x,y,表示x和y之间有一条边相连。Output让吉丽满意的方案数。SampleInput7125725235645SampleOutp...

    02015年4月2日978树形动规
  • 【NOIP模拟赛】小奇的仓库

    【NOIP模拟赛】小奇的仓库

    原题:【East!_XI】第一个问题2015年10月4日hzwer改写了题面【题目背景】小奇采的矿实在太多了,它准备在喵星系建个矿石仓库。令它无语的是,喵星系的货运飞船引擎还停留在上元时代!【问题描述】喵星系有n个星球,星球以及星球间的航线形成一棵树。从星球a到星球b要花费[dis(a,b)XorM]秒。(dis(a,b)表示ab间的航线长度,Xor为位运算中的异或)为了给仓库选址,小奇想知道,星球i(1<=i<=n)到其它所有星球花费的时...

    22015年3月30日935树形动规
  • 【cf519X】Codeforces Round #294 (Div. 2)

    【cf519X】Codeforces Round #294 (Div. 2)

    【cf519A】AandBandChess模拟[crayon-58d3665009174471402620/]【cf519B】AandBandCompilationErrors排序,双指针对比用个hash/map统计下元素出现次数[crayon-58d366500917e045226595/]【cf519C】AandBandTeamTraining实际上答案是min(n,m,(m+n)/3)我分类讨论了TAT还是很好yy的[crayon-58d3665009188137993365/]【cf519D】AandBandInterestingSubstringsa[i][j]表示前缀和为i,字母j为末尾的前缀数量每次查询...

  • 【bzoj1369】[Baltic2003]Gem

    【bzoj1369】[Baltic2003]Gem

    Description给出一棵树,要求你为树上的结点标上权值,权值可以是任意的正整数唯一的限制条件是相临的两个结点不能标上相同的权值,要求一种方案,使得整棵树的总价值最小。Input先给出一个数字N,代表树上有N个点,N<=10000下面N-1行,代表两个点相连Output最小的总权值SampleInput107512178941975610293SampleOutput14题解WJMZBMR:这题首先是不能用奇偶层染色的办法来做的,我构造出了至少需要1-3的反例,同时...

    12015年2月27日1,019树形动规
  • 【codechef】February Lunchtime 2015

    【codechef】February Lunchtime 2015

    懒得开多篇了LuckyFour 这题在逗我么[crayon-58d36650222e0179070546/]TheWarehouse发现实际上把一个东西移动到一个位置相当于不断做代价为1的交换所以只要枚举给3种字母赋权,求逆序对最小值即可[crayon-58d36650222f2690048418/]Heavy-lightDecompositions设f[i][j]表示i为根的子树,后代到i经过轻边数量不超过j树形dp,要用到前缀后缀积/逆元。。。[crayon-58d36650222fd968749264/]  TheFirstCube 一眼分...

  • 【bzoj2815】[ZJOI2012]灾难

    【bzoj2815】[ZJOI2012]灾难

    小强和阿米巴0.0fhq神犇的题==http://fanhq666.blog.163.com/blog/static/8194342620124274154996/[crayon-58d3665022b1e438073491/] 

  • 【bzoj3162】独钓寒江雪

    【bzoj3162】独钓寒江雪

    Description题解参照2007杨弋论文vfk的博客http://vfleaking.blog.163.com/blog/static/17480763420134452440444/太神了orzorzorz[crayon-58d3665023435524269921/]  

    72015年1月28日1,524树形动规,哈希表
  • 【bzoj3611】[Heoi2014]大工程

    【bzoj3611】[Heoi2014]大工程

    题面和题解见http://www.cnblogs.com/zyfzyf/p/4231356.html[crayon-58d3665024190275413468/]  

  • 【bzoj2286】[Sdoi2011]消耗战

    【bzoj2286】[Sdoi2011]消耗战

    Description在一场战争中,战场由n个岛屿和n-1个桥梁组成,保证每两个岛屿间有且仅有一条路径可达。现在,我军已经侦查到敌军的总部在编号为1的岛屿,而且他们已经没有足够多的能源维系战斗,我军胜利在望。已知在其他k个岛屿上有丰富能源,为了防止敌军获取能源,我军的任务是炸毁一些桥梁,使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同,所以炸毁不同的桥梁有不同的代价,我军希望在满足目标的同时使得总...

    32015年1月20日2,961虚树,树形动规
  • 【bzoj3696】【FJ2014集训】化合物

    【bzoj3696】【FJ2014集训】化合物

    Description   首长NOI惨跪,于是去念文化课了。现在,他面对一道化学题。这题的来源是因为在一个奇怪的学校两个化竞党在玩一个奇怪的博弈论游戏。这个游戏很蛋疼,我相信你们也没有兴趣听。由于这个游戏涉及博弈论,因此化竞的同学就要求首长求一个类似SG函数的值。他们手中有一种非常神奇的化合物,它的分子由N个原子组成(不要在意一个原子可能和及其多个原子成键这个细节)。这个分子构成一个树结构,1号分子为根。 ...

    02015年1月4日1,659树形动规,最近公共祖先