树 - Page 3 - hzwer.com

「BZOJ2157」旅游
DescriptionRay乐忠于旅游，这次他来到了T城。T城是一个水上城市，一共有N个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T城的任意两个景点之间有且只有一条路径。换句话说，T城中只有N−1座桥。Ray发现，有些桥上可以看到美丽的景色，让人心情愉悦，但有些桥狭窄泥泞，令人烦躁。于是，他给每座桥定义一个愉悦度w，也就是说，Ray经过这座桥会增加w的愉悦度，这或许是正的也可能是负的...
62015年2月15日4,983link cut tree

「BZOJ2815」[ZJOI2012] 灾难
小强和阿米巴0.0fhq神犇的题==http://fanhq666.blog.163.com/blog/static/8194342620124274154996/[crayon-674064c8620d4854496388/]
22015年2月5日6,962树形动规,拓扑排序,最近公共祖先
「BZOJ3611」[HEOI2014] 大工程
题面和题解见http://www.cnblogs.com/zyfzyf/p/4231356.html[crayon-674064c862af1937139863/]
22015年1月20日6,424dfs序,虚树,树形动规,最近公共祖先
「BZOJ2286」[SDOI2011] 消耗战
Description在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总...
22015年1月20日8,311虚树,树形动规
「BZOJ2654」tree
Description　　给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。题目保证有解。Input　　第一行V,E,need分别表示点数，边数和需要的白色边数。接下来E行每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。Output　　一行表示所求生成树的边权和。SampleInput22101110120SampleOutput2HINT数据规模和约定0:V<=101,2,3:V<=150,..,19:V<...
42015年1月16日7,727kruskal,二分法
「点分治练习」[hdu4812] multik
「问题描述」给定一棵n个点的树,每个点有权值Vi问是否存在一条路径使得路径上所有点的权值乘积mod(10^6+3)为K输出路径的首尾标号,若有多解,输出字典序最小的解「输入格式」第一行两个数n,K第二行n个数,表示vi接下来n-1行每行两个数x,y表示一条边「输出格式」输出两个数a,b(a<b),无解输出”Nosolution”(不含引号)。「样例输入」5602523312132425「样例输出」34「数据规模与约定」对于100%的数据,有1≤n≤10^5,0≤K≤10^6+2...
62015年1月12日6,277点分治,乘法逆元
「点分治练习」不虚就是要AK
「问题描述」czy很火，因为又有人说他虚了为了证明他不虚,他决定要在这次比赛AK现在他正在和别人玩一个游戏:在一棵树上随机取两个点(两个点可以相同)如果这两个点的距离是4的倍数,那么算czy赢,否则对方赢现在czy想知道他能获胜的概率以即约分数形式输出这个概率(即”a/b”的形式,其中a和b必须互质。如果概率为1,输出”1/1”)「输入格式」多组数据,对于每组数据第一行一个数n,表示树上的节点个数接下来n-1条边a,b,c描述a到b有一条...
52015年1月10日6,064点分治
「点分治练习」boatherds
「问题描述」询问一颗树上距离为K的点对是否存在「输入格式」第一行两个整数n,m接下来n-1条边a,b,c描述a到b有一条长度为c的路径接下来m行每行询问一个K「输出格式」对于每个K每行输出一个答案存在输出”AYE”,否则输出”NYE”(不包含引号)「样例输入」2212112「样例输出」AYENYE「数据规模与约定」对于30%的数据,有1≤n≤100对于60%的数据,有1≤n≤10^31≤m≤50对于100%的数据,有1≤n≤10^4,1≤m≤100,1≤c≤1000,1...
12015年1月10日4,045STL,点分治
「BZOJ3696」「FJ2014集训」化合物
Description 首长NOI惨跪，于是去念文化课了。现在，他面对一道化学题。这题的来源是因为在一个奇怪的学校两个化竞党在玩一个奇怪的博弈论游戏。这个游戏很蛋疼，我相信你们也没有兴趣听。由于这个游戏涉及博弈论，因此化竞的同学就要求首长求一个类似SG函数的值。他们手中有一种非常神奇的化合物，它的分子由N个原子组成（不要在意一个原子可能和及其多个原子成键这个细节）。这个分子构成一个树结构，1号分子为根。 ...
02015年1月4日4,465树形动规,最近公共祖先
「SPOJ1825」Free tour II
Afterthesuccessof2ndanniversary(takealookatproblemFTOURformoredetails),this3rdyear,TravelAgentSPOJgoesonwithanotherdiscounttour.ThetourwillbeheldonICPCisland,amiraculousoneonthePacificOcean.WelistNplaces(indexedfrom1toN)wherethevisitorscanhaveatrip.Eachroadconnectingthemhasaninterestvalue,andthisvaluecanbenegative(ifthereisnothinginterestingtoviewthere).Simply,theseNplaces...
32015年1月1日5,136点分治
「POJ3237」Tree
DescriptionYouaregivenatreewithNnodes.Thetree’snodesarenumbered1throughNanditsedgesarenumbered1throughN−1.Eachedgeisassociatedwithaweight.Thenyouaretoexecuteaseriesofinstructionsonthetree.Theinstructionscanbeoneofthefollowingforms:CHANGEivChangetheweightoftheithedgetovNEGATEabNegatetheweightofeveryedgeonthepathfromatobQUERYabFindthemaximumweightofedgesonthepathfromat...
02014年12月21日5,992线段树,树链剖分
「BZOJ4016」[FJOI2014] 最短路径树问题
cxjyxx_me:先求一个最短路图然后再这个图上dfs对于一个点的所有出点按编号从小到大dfs这样可以保证dfs树就是题目要求的树然后在这棵树上跑树分治f[i][j][2]表示前i棵子树从根出发链长为j[0：最长长度][1:这个长度条件下的方案数]对于第i+1棵子树单独跑一个f’[i][j][2]意义一样枚举这颗子树上链长和f一起更新答案然后用f‘更新f[crayon-674064c8796b9426822732/] ...
52014年12月15日7,795STL,dijkstra,点分治