夢に僕らで帆を張って
来るべき日のために夜を超え

标签 树 下的文章

November 11, 2019

洛谷P3177/HAOI2015 树上染色

题意有一棵点数为$N$的树,树边有边权。给你一个在$0 \sim N$之内的正整数$K$,你要在这棵树中选择$K$个点,将其染成黑色,并将其他 的$N-K$个点染成白色将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间的距离的和的受益。问受益最大值是多少数据范围:$0 \le k \le n \le 2000$题解因为计算答案时需要对整颗树考虑,而一条边的贡献为$$一侧的黑/白色点数...
November 11, 2019

洛谷P1270 “访问”美术馆

题意经过数月的精心准备,Peer Brelstet,一个出了名的盗画者,准备开始他的下一个行动。艺术馆的结构,每条走廊要么分叉为两条走廊,要么通向一个展览室。Peer知道每个展室里藏画的数量,并且他精确测量了通过每条走廊的时间。由于经验老到,他拿下一幅画需要5秒的时间。你的任务是编一个程序,计算在警察赶来之前,他最多能偷到多少幅画题解树上背包注意读入代码:#include<iostre...
November 11, 2019

洛谷P2014 选课

题意现在有N门功课,每门课有个学分,每门课有一门或没有直接先修课(若课程$a$是课程$b$的先修课即只有学完了课程$a$,才能学习课程$b$)。一个学生要从这些课程里选择$M$门课程学习,问他能获得的最大学分是多少?数据范围:$1 \le n,m \le 300$题解树上背包用$dp[u][i]$表示以$u$为根的子树中选择$j$门课的最大学分代码:#include<iostream&...
November 11, 2019

洛谷P1122 最大子树和

题意求树上联通块的最大权值和数据范围:$n \le 16000$题解树形$\text{dp}$用$dp[u]$表示以$u$为根的子树中的最大权值和代码:#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; co...
November 6, 2019

洛谷P2633 Count on a tree

题意给出一棵带点权的树,$m$个询问,求$u \rightarrow v$路径上第$k$小的点权数据范围:$n,m \le 100000$ [强制在线]题解树上静态区间第$k$小,使用主席树维护序列上的主席树使用的是前缀和思想;那么自然,在树上的情况就要用到树上前缀和建树的时候在其父节点的基础上拷贝包含$u \rightarrow v$路径上的信息的应为$$T[u]+T[v]-T[lca(u...
November 5, 2019

洛谷P4427/BJOI2018 求和

题意给出一棵树,$m$个询问,求从点$u$到点$v$的路径上所有节点深度的$k$次方和$\bmod \ 998244353$数据范围:$1 \le n,m \le 300000,1 \le k \le 50$题解对每一个$k$求一个树上前缀和答案为$$u+v-lca(u,v)-fa[lca(u,v)]$$代码:#include<iostream> #include<cstd...
November 5, 2019

洛谷P1505/国家集训队 旅游

题意给出一颗有边权的树,有$5$种操作:覆盖一条边的边权将$u$到$v$路径上的边权变为相反数询问$u$到$v$路径上的边权和询问$u$到$v$路径上的边权最大值询问$u$到$v$路径上的边权最小值数据范围:$n,m \le 20000$题解考虑将边权下放,随后此问题可用树链剖分解决线段树维护和,最大值,最小值及相反数标记区间处理的时候注意是否处理到$\text{LCA}$代码:#inclu...
November 4, 2019

洛谷P3313/SDOI2014 旅行

题意略数据范围:$n,q,c \le 10^5$题解由于要对每个宗教开一个线段树维护,空间过大,考虑动态开点线段树每颗线段树维护最大值以及区间和,对于修改操作,直接删除并新建节点之后在树剖上进行即可代码:#include<iostream> #include<cstdio> #include<algorithm> using namespace std; ...