原文链接www.cnblogs.com/zhouzhendong/p/UOJ335.htmlCLY大爷随手切这种题。日常被CLY吊打系列。首先从pruffer编码的角度考虑这个问题。pruffer编码的长度为$n-2$，如果点$i$在pruffer编码中出现了$d_i-1$次，那么点$i$的度数就是$d_i$，对答案的...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ7.html这题是Unknown的弱化版。如果这个问题出在序列上，那么显然可以CDQ分治+斜率优化+凸包上二分来做。那么它出在树上？点分治。写挂了好多地方调了好久，自闭了。#pragmaGCCoptimize("Ofast","...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ276.html首先，读入的时候就将所有的$w_i$减掉$k$。于是我们要求的就是平均值最接近0的。直接点分治，然后得到一些一端为当前点分中心的路径，设$a,b$为其中两条路径，设$v_a,v_b$为路径的边权和，$t_a,t_...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ347.html　　有三棵树，边有边权。　　对于所有点对(x,y)求在三棵树上x到y的距离之和的最大值。　　点数<=100000　　我自闭了。　　在此之前，我没写过边分治，只写过一次虚树。　　我自闭了。 　　一棵...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ23.html　　给定一个有n个节点的仙人掌（可能有重边）。　　对于所有的$L(1leqLleqn-1)$，求出有多少不同的从节点1出发的包含L条边的简单路径。简单路径是指不重复经过任意一点。　　$nleq10^5$　　首先我们...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ33.html　　首先我们把问题转化成处理一个数组ans，其中ans[i]表示d(u,a)和d(v,a)同时为i的倍数的(u,v)个数。（最后求答案的时候只要莫比乌斯反演回来就好了。）　　注意一下我的代码中对于(u,v)有祖先关...

原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ1095.html　　有N个点，每一个点是黑色或者白色，一开始所有点的颜色都是黑色。有M次操作，每次操作有两种类型：1.修改一个点的颜色；2.查询树上所有黑色点对之间的距离最大值。　　$Nleq100000,mleq50000...

原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ3451.html　　给定一棵有$n$个节点的树，在树上随机点分治，问消耗时间的期望。　　计算点分治耗时由如下函数给出：Time=0Solve(T){Time+=|T|if(|T|=1)thenreturn;x=一个随机节点i...

原文链接https://www.cnblogs.com/zhouzhendong/p/9161557.html　　给定一个数$n(nleq10^{1500000})$,求满足$(prodb_i)geqn$的$min(sumb_i)$。　　这题是下面链接中那题的加强版。　　BZOJ1263[SCOI2006]整数划分高精...

原文链接http://www.cnblogs.com/zhouzhendong/p/8847145.html　　一个有$n$个节点$m$条边的有向图，每条边连接了$a_i$和$b_i$，花费为$c_i$。　　每次经过某一条边就要花费该边的$c_i$。　　第$i$条边耗时为$j$的概率为$p_{i,j}$。　　现在你从$...

原文链接http://www.cnblogs.com/zhouzhendong/p/8835443.html　　有$n$个球，球有$m$种颜色，分别编号为$1cdotsm$，现在让你从中拿$k$个球，问拿到的球的颜色所构成的可重集合有多少种不同的可能。　　注意同种颜色球是等价的，但是两个颜色为$x$的球不等价于一个。　...

原文链接http://www.cnblogs.com/zhouzhendong/p/8830036.html　　定义二元运算$opt$满足$$xopty=egin{cases}x+y&ext{$(x<y)$}\x-y&ext{$(xgeqy)$}end{cases}$$　　现在给定一个长为$n$...

原文链接http://www.cnblogs.com/zhouzhendong/p/8684027.html　　有$n$个物品，第$i$个物品的体积为$w_i$。　　令$cnt_{i,j}$表示不取第$i$个物品，占用$j$体积的方案总数。　　每一个物品只能取或者不取。　　让你对于每一个$i,j(1leqileqn,1...

原文链接http://www.cnblogs.com/zhouzhendong/p/8683831.html　　有$n$个点，有$m$条边。有$T$个时间段。其中第$i$条边连接节点$x_i,y_i$，并且在$start_i$时刻出现，在$end_i$时刻消失。问每一个时刻的图是不是二分图。　　$nleq10^5,ml...

原文链接https://www.cnblogs.com/zhouzhendong/p/8682572.html　　平面上有$n(nleq2imes10^5)$个整点（坐标范围在$[0,10^9]$之间）。　　第$i$个点$p_i$的坐标是$(x_i,y_i)$。　　如果有一对点$p_i$和$p_j$，满足$x_i<...