- 2023-05-19【做题记录】SHOI 2012 魔法树
有两个操作:将\(u\)到\(v\)路径增加\(k\)询问\(u\)节点的子树和显然,我们可以用树链剖分+线段树来做。代码:#include<cstdlib>#include<cstdio>#include<cctype>#include<algorithm>typedeflonglongLL;typedefunsignedlonglongULL;namespaceFastIo{
- 2023-05-19【做题记录】CodeForces343D Water Tree
题面翻译给出一棵以\(1\)为根节点的\(n\)个节点的有根树。每个点有一个权值,初始为\(0\)。\(m\)次操作。操作有\(3\)种:将点\(u\)和其子树上的所有节点的权值改为\(1\)。将点\(u\)到\(1\)的路径上的所有节点的权值改为\(0\)。询问点\(u\)的权值。\(1\le
- 2023-05-14[USACO11DEC]Grass Planting G
树链剖分题目注意:要把边权转为点权计算两条链时,这两条链的公共点被额外算了一次,需要减去它#include<cstdlib>#include<cstring>#include<cstdio>#include<cctype>#include<algorithm>typedeflonglongLL;typedefunsignedlonglongULL;namespaceFastIo{typ
- 2023-05-14HAOI 2015 树上操作
有一棵点数为N的树,以点1为根,且树有点权。然后有M个操作,分为三种:操作1:把某个节点x的点权增加a。操作2:把某个节点x为根的子树中所有点的点权都增加a。操作3:询问某个节点x到根的路径中所有点的点权和。做法:树链剖分+线段树,板子题#include<cstdlib>#inc
- 2023-05-14ZJOI2008 树的统计
这是一道比树链剖分板子还板子的题目。操作:我们将以下面的形式来要求你对这棵树完成一些操作:CHANGEut:把节点\(u\)权值改为\(t\);QMAXuv:询问点\(u\)到点\(v\)路径上的节点的最大权值;QSUMuv:询问点\(u\)到点\(v\)路径上的节点的权值和。注意:从点\(u\)