树上倍增 - hzwer.com

「CF1229X」Codeforces Round #588
A.MarcinandTrainingCamp若A觉得自己没有B强，B向A连边度数为0的点，是觉得自己比其它人都强的，把它们依此拓扑排序删除[crayon-5da93a91504be634839704/]B.KamilandMakingaStream从一个点向上走，区间gcd单调下降，且最多变化log次可以用树上倍增维护区间gcd，枚举每个点往上二分跳，暴力统计答案更简单的做法是用vector维护一个点往上的不同gcd，以及它们贡献答案的次数，这个vector大小是logdfs暴力往儿子转移倍增：...
02019年10月3日158树上倍增,拓扑排序,最大公约数与最小公倍数

程序设计实习实验班2017作业(算法作业19, 20, 21)
一些以前做过的就不再贴了AFunnyStoneGame发现每一堆的每个石子之间都是相互独立的[crayon-5da93a91516e8683516386/]nnimn阶nim和，在二进制下，每一位求和后对(n+1)取模[crayon-5da93a91516f3094224106/]一个水水的序列在建操作树的过程中就能顺便维护信息每次新加入节点的时候维护一下这个点的倍增数组，询问的时候直接向上倍增[crayon-5da93a91516f8772211716/]「poj1523」SPF求割点，并且求删去割点后的连通分量个数[cr...
02017年6月24日2,403状压动规,树状数组,博弈论,树上倍增,矩阵乘法
「CF519X」Codeforces Round #294 (Div. 2)
「cf519A」AandBandChess模拟[crayon-5da93a9151d33512889576/]「cf519B」AandBandCompilationErrors排序，双指针对比用个hash/map统计下元素出现次数[crayon-5da93a9151d3d755016129/]「cf519C」AandBandTeamTraining实际上答案是min(n,m,(m+n)/3)我分类讨论了TAT还是很好yy的[crayon-5da93a9151d42806527785/]「cf519D」AandBandInterestingSubstringsa[i][j]表示前缀和为i，字母j为末尾的前缀数量每次查询...
12015年2月28日2,385模拟,STL,树形动规,树上倍增,最近公共祖先
「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日4,218dfs序,线段树,树上倍增
NOIP2012开车旅行
描述小A和小B决定利用假期外出旅行，他们将想去的城市从1到N编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市i的海拔高度为Hi，城市i和城市j之间的距离d[i,j]恰好是这两个城市海拔高度之差的绝对值，即d[i,j]=|Hi-Hj|。旅行过程中，小A和小B轮流开车，第一天小A开车，之后每天轮换一次。他们计划选择一个城市S作为起点，一直向东行驶，并且最多行驶X公里就结束旅行。小A和小B的...
22014年8月31日5,495树上倍增
「JoyOI1577」泥泞的道路
描述Description公园中有n个景点，编号1~n，并由m条双向道路相连。由于昨天下雨，导致公园中的马路泥泞不堪，每条道路都有一个泥泞程度w。现有Q个游客依次向你求助，想从景点X走到景点Y，他希望找到一条道路，使得经过道路泥泞程度的最大值尽量小。你能设计一个在线算法，帮他们找到方案吗？输入格式InputFormat第一行两个正整数n和m，表示景点数和道路数。随后m行每行三个正整数x、y、w，用来描述一条道路，它连接x和y景点并...
02014年7月26日2,260广度搜索,树上倍增
「BZOJ1977」[BJ2010组队] 次小生成树 Tree
Description小C最近学了很多最小生成树的算法，Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时，小P又来泼小C冷水了。小P说，让小C求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是EM，严格次小生成树选择的边集是ES，那么需要满足：(value(e)表示边e的权值) 这下小C蒙了，他找到了你，希望你帮他解决这个问题。Input第一行包含两个整数N和...
12014年4月28日4,402kruskal,树上倍增
NOIP2013货车运输
题目描述DescriptionA国有n座城市，编号从1到n，城市之间有m条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有q辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。输入描述InputDescription第一行有两个用一个空格隔开的整数n，m，表示A国有n座城市和m条道路。接下来m行每行3个整数x、y、z，每两个整数之间用一个空格隔开，表示从x号城市到y号城市有一条限重为z的道路。注意：x...
142014年4月9日23,103spfa,kruskal,树上倍增