标签 - 树链剖分

? 解题记录 ? ? FFT|NTT ? ? 树链剖分 ? ? 虚树 ? ? 组合数 ?    2019-03-18 12:09:49    1141    0    3
题目描述 给你一棵n个点的树,每一个点有个颜色ci" role="presentation" style="position: relative;">cicic_i。定义一种颜色的树是:把该颜色的点两两路径上的点和边都拿出来构成的图形。你可以选出k" role="presentation" style="position: relative;">kkk种颜色来,求:有多少种方案可以使每种颜色交集产生的树非空。对k∈[1,m]" role="presentation" style="position: relative;">k∈[1,m]k∈[1,m]k
? 解题记录 ? ? LOJ ? ? 树链剖分 ? ? FFT|NTT ? ? 动态规划 ?    2019-03-14 11:31:06    734    0    0
题目链接:传送门 题解:不难发现,我们有一个优秀的N2N^2的dpdp做法,记录f(i,j,0/1)f(i,j,0/1)表示ii子树内选jj个,当前根选没选。 我们要知道分治NTTNTT的复杂度:对于kk个总度数∑deg=k\sum deg=k的多项式来说,计算它们乘积的复杂度可以做到:O((∑deg)log(∑deg)logk)O((\sum deg)log(\sum deg)logk)。 因此,我们采用重链剖分,先转移所有轻链。 不难发现, g(u,0)=∏v∈son(g(v,0)+g(v,1))g(u,0)=\prod_{v\in son} (g(v,0)+g(v,1))
? 解题记录 ? ? BZOJ ? ? 整体二分 ? ? 树状数组 ? ? 树链剖分 ?    2019-01-05 11:01:15    667    0    0
【题目描述】风见幽香非常喜欢玩一个叫做 osu!的游戏,其中她最喜欢玩的模式就是接水果。 由于她已经DT FC 了The big black,  她觉得这个游戏太简单了,于是发明了一个更加难的版本。首先有一个地图,是一棵由 n 个顶点、n-1 条边组成的树(例如图 1给出的树包含 8 个顶点、7 条边)。这颗树上有 P 个盘子,每个盘子实际上是一条路径(例如图 1 中顶点 6 到顶点 8 的路径),并且每个盘子还有一个权值。第 i 个盘子就是顶点a_i到顶点b_i的路径(由于是树,所以从a_i到b_i的路径是唯一的),权值为c_i。接下来依次会有Q个水果掉下来,每个水果本质上也是一条
? 解题记录 ? ? 模板 ? ? 动态规划 ? ? 树链剖分 ?    2018-12-10 11:15:59    630    0    0
题目描述给定一棵n个点的树,点带点权。 有m次操作,每次操作给定x,y,表示修改点x的权值为y。 你需要在每次操作之后求出这棵树的最大权独立集的权值大小。 输入输出格式输入格式:   第一行,n,m,分别代表点数和操作数。 第二行,V1​,V2​,...,Vn​,代表nn个点的权值。 接下来n−1行,x,y,描述这棵树的n−1条边。 接下来m行,x,y,修改点x的权值为y。   输出格式:   对于每个操作输出一行一个整数,代表这次操作后的树上最大权独立集。 保证答案在int范围内   输入输出样例输入样例#1: 复制10 10 -11 80
? 解题记录 ? ? 洛谷 ? ? 树链剖分 ? ? 差分 ?    2018-10-09 14:25:45    380    0    0
小C同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。 这个游戏的地图可以看作一棵包含  个结点和  条边的树,每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从  到  的连续正整数。 现在有  个玩家,第  个玩家的起点为 ,终点为 。每天打卡任务开始时,所有玩家在第  秒同时从自己的起点出发,以每秒跑一条边的速度,不间断地沿着最
? 解题记录 ? ? 树链剖分 ? ? 差分 ?    2018-04-04 19:01:19    437    0    0
题目描述松鼠的新家是一棵树,前几天刚刚装修了新家,新家有n个房间,并且有n-1根树枝连接,每个房间都可以相互到达,且俩个房间之间的路线都是唯一的。天哪,他居然真的住在”树“上。 松鼠想邀请小熊维尼前来参观,并且还指定一份参观指南,他希望维尼能够按照他的指南顺序,先去a1,再去a2,......,最后到an,去参观新家。可是这样会导致维尼重复走很多房间,懒惰的维尼不停地推辞。可是松鼠告诉他,每走到一个房间,他就可以从房间拿一块糖果吃。 维尼是个馋家伙,立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃,他需要在每一个房间各放至少多少个糖果。 因为松鼠参观指南上的最后一个房间an是餐厅,餐厅里他准
? 解题记录 ? ? BZOJ ? ? 树链剖分 ? ? 线段树 ? ? 补档计划第一期 ?    2018-01-28 11:04:37    420    0    0
Description  一棵树上有n个节点,编号分别为1到n,每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成 一些操作: I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 I II. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意:从点u到点v的路径上的节点包括u和v本身 Input  输入的第一行为一个整数n,表示节点的个数。接下来n – 1行,每行2个整数a和b,表示节点a和节点b之间有 一条边相连。接下来n行,每行一个整数,第i行的整数wi表示节点i的权值。接下来1行,为一个整
? 解题记录 ? ? 洛谷 ? ? 树链剖分 ? ? 线段树 ?    2018-01-23 23:07:56    422    0    0
题目描述给出N个点的一棵树(N-1条边),节点有白有黑,初始全为白 有两种操作: 0 i : 改变某点的颜色(原来是黑的变白,原来是白的变黑) 1 v : 询问1到v的路径上的第一个黑点,若无,输出-1 输入输出格式输入格式:   第一行 N,Q,表示N个点和Q个操作 第二行到第N行N-1条无向边 再之后Q行,每行一个操作"0 i" 或者"1 v" (1 ≤ i, v ≤ N).   输出格式:   对每个1 v操作输出结果   输入输出样例输入样例#1: 复制9 8 1 2 1 3 2 4 2 9 5 9 7 9 8 9 6 8 1 3 0 8 1 6
? 解题记录 ? ? 洛谷 ? ? 树链剖分 ? ? 线段树 ?    2018-01-23 20:01:21    664    0    0
题目背景数据规模和spoj上有所不同题目描述给定一棵n个节点的树,有两个操作: CHANGE i ti 把第i条边的边权变成ti QUERY a b 输出从a到b的路径中最大的边权,当a=b的时候,输出0输入输出格式输入格式:   第一行输入一个n,表示节点个数 第二行到第n行每行输入三个数,ui,vi,wi,分别表示 ui,vi有一条边,边权是wi 第n+1行开始,一共有不定数量行,每一行分别有以下三种可能 CHANGE,QUERY同题意所述 DONE表示输入结束   输出格式:   对于每个QUERY操作,输出一个数,表示a b之间边权最大值   输
题目描述如题,已知一棵包含N个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作: 操作1: 格式: 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z 操作2: 格式: 2 x y 表示求树从x到y结点最短路径上所有节点的值之和 操作3: 格式: 3 x z 表示将以x为根节点的子树内所有节点值都加上z 操作4: 格式: 4 x 表示求以x为根节点的子树内所有节点值之和 输入输出格式输入格式:   第一行包含4个正整数N、M、R、P,分别表示树的结点个数、操作个数、根节点序号和取模数(即所有的输出结果均对此取模)。 接下来一行包含N个非负整数,分别依次