题面原题链接思路我们考虑如何判断一对\(T_1,T_2\)是否合法。首先，我们可以发现\(T_2\)上的边权只能有至多一组合法解，这是因为对于任意一条边连接\(u,v\)，它的边权必然是\(dis_1(u,v)\)，所以事实上我们是没有权限给\(T_2\)任意赋权的，这样题目就简单了一些。那么，我们如何

一种树上链问题转二维数点问题的方法例题：2024.11.21T3焰硝庭火舞,P3242[HNOI2015]接水果使用场景：一个（组）元素对包含他的链造成影响。静态问题使用方法：首先求出每个点的DFS序，那么每个点的子树内所有点的DFS序连续，记\(L_u,R_u\)为\(u\)子树内DFS序的最小值与最

期望得分：100+100+0+10=210实际得分：100+80+0+10=190好困。。T1被硬控了很久。看着就像诈骗题，观察大样例发，答案就是\(a_1-a_2\)，特判\(n=1\)的情况。证明的话，感觉就是后面的数，贡献成正数和负数应该是数量相同的，所以就抵消了，第一个数只能贡献成正数，第二个数只能贡献成负的。T

树上的背包问题，也就是背包问题与树形DP的结合。例题：P2014[CTSC1997]选课有\(n\)门课程，第\(i\)门课程的学分为\(a_i\)，每门课程有零门或一门先修课，有先修课的课程需要先学完其先修课，才能学习该课程。一位学生要学习\(m\)门课程，求其能获得的最多学分数。数据范围：\(n,m

近年的NOIP，对于树上差分的题目时有出现：（NOIP2015《运输计划》，NOIP2016《天天爱跑步》）。这些题目都要知道在树上从某个点到另一个点的所有路径。但是，暴力求解这种题目经常会TLE。这种题目需要使用树上差分。在讲树上差分之前，首先需要知道树的以下两个性质：任意两个节点之间

求区间第k小值静态分块排序划分树动态主席树平衡树子树求交树上颜色问题统计颜色数量对于子树\(x\)，子树内同种颜色的点只有深度最浅的对子树外有贡献#3628.「2021集训队互测」树上的孤独贡献上传：对于\(x\)，设它同颜色祖先为\(p\)，则\(x\)对路径\(p\thicksimx\)上的

LCA，最近公共祖先问题。给定一颗有根树，若节点k既是节点x的祖先，又是节点y的祖先，则称k是\(\lbrackx,y\rbrack\)的公共祖先。在\(\lbrackx,y\rbrack\)的所有公共祖先中，深度最大的称为最近公共祖先，记作\(\operatorname*{LCA}(x,y)\)。\(\operatorname*{LCA}(x,y

P2685[TJOI2012]桥首先求出一个最短路树，显然只能删除树上的边才对答案有影响。最短路树有很多，任意求一个可以吗？可以，因为删除一条边后就可以走另一个最短路树了。枚举删除哪一条边并不好计算。考虑最后我们最短路一定是\(1\tol_x\tox\toy\tor_y\ton\)的样子，所以我们考

树上问题开题顺序：\(AC\)\(A\)CF600ELomsatgelral题解\(B\)CF708CCentroids\(C\)CF1706EQpwoeirutandVertices题解\(D\)luoguP2491[SDOI2011]消防\(E\)luoguP4253[SCOI2015]小凸玩密室\(F\)luoguP8890[入门赛#7]打ACM最快乐的就是滚榜读队名

原题链接\(首先注意到用点维护dp值非常地难做\)\(我们无法通过点直接维护树上的每个节点的染色\)\(因为这样做的复杂度为O（2^n）\)\(我们考虑到通过枚举边来处理\)\(对于每条边枚举它两边的黑色和白色节点数\)\(那么对该条边被经过的数量为两边的黑色节点数和白色节点数的乘

5我们还没介绍过涛哥居住的城堡呢涛哥所在的城堡是一个不算很大，但是人比较多的城堡，城堡里除了B先生，好像只有一个厨师，两个人轮流来看守城堡里的秩序这个城堡不能算太差，可惜它有太多莫名奇妙的规章制度每天早上，城堡里的人都要在城堡外举行神秘的热身仪式来开启新的一天，回到城

问题引出:给出\(n\)个点的树，求出分别以不同的\(i\)为根时，所有结点深度的和，根节点的深度为\(0\)。首先我们有个自然的暴力思路,也就是以每个节点为根节点做一遍\(dfs\)这样的复杂度是\(O(n^2)\)级别的,所以要进行优化看下图:我们首先假设每个节点具有点权,明显这

题意简述给你一棵\(n\)个结点的树，编号为\(1\simn\)，求有多少路径\(\operatorname{Path}(u\rightarrowv)\)，满足\(u=\max\{x\midx\in\operatorname{Path}(u\rightarrowv)\}\)，\(v=\min\{x\midx\in\operatorname{Path}(u\rightarrowv)\}\)。

1.点的差分    求路径u-v上的点被经过的次数。    cnt[ x]代表点x经过的次数。    核心代码：cnt[n]++;cnt[v]++;cnt[lca]--;cnt[fa[lca]]--; 2.边的差分    求u-v路径上每一条边经过的次数。    cnt[ x

acam作为多模匹配算法，很多东西与kmp相同，另外增添了fail树上操作的关键性质。朴素acam就是trie树，fail指针就是在当前node找一个后缀，使得在其他串存在一个前缀是这个后缀（类似kmp）。trie图，就是简单优化了这个"树上乱跳"的过程，补全每个节点的儿子，类似于路径压缩。其实

3涛哥在树上的生活也并不总是一帆风顺的，毕竟是在野外，就算有时候找不到吃的或者水源，但这些危险比起大自然的种种威胁来，还是太过逊色了涛哥发现，并不是所有的线段树都能够比作水井，有些线段树积极的很，一有操作马上就会下放，但是有的线段树就像睡着了一样，使劲踹它两脚，它才像挤牙膏一样

T1题面有一个\(n\)个节点的树，根节点为\(1\)，令叶子节点数为\(m\)，叶子节点的权值为一个\(1\)到\(m\)的排列。Alice和Bob在树上玩游戏，两人从根节点开始，Alice先手的轮流的行走\(u\to\text{son}(u)\)的路径直到抵达叶子节点。叶子的权值为本次游戏的得分。Alice希望最大

1在涛哥12岁之前，一切都像正常人平静的生活一般，涛哥正常地在房间里敲代码，正常地打模拟赛，正常地改题，正常地写闲话直到涛哥十二岁的时候，一切都变了那天上午，我完全没有意识到接下来的一天会发生什么，因为涛哥仍然像往常一样在房间里和我们聊天B先生出现了，说自己身为国家之重臣，需

天天爱跑步假设现在又一棵树如果一个人要从\(3\)跑到\(5\),那么如果在\(2\)点的观察员要满足\(w[2]=dep[2]-dep[3]\),如果在点\(4\)的观察员要满足\(w[4]=dep[fa[lca]]-dep[3]+dep[lca]-dep[4]\),简单来说就是如果处于\(i\)点的观察员可以观察到,那么要

跳跃带修可以考虑\(\sqrt{n}\)分块维护若是跳次数超多可以考虑倍增维护很多有循环/置换环的东西可以把一次转换看成“跳跃”dp抽象网格图抽象：把状态看做网格图上的点，观察性质分层dp抽象：把每层画出，把转移边画出，看是否能通过平移等做内联dp子集枚举for(S=(1<<n

首先拿到本题第一时间能抽象出的题意相关内容为树上路径覆盖。然后考虑怎么做，因为树上路径覆盖问题为树上组合优化问题，树上组合优化大概有两种思路树上贪心&树形dp。对于树上路径覆盖问题，这两种思路就为树上贪心&树上插头dp。看到数据范围为\(n\leq200000\)，如果是dp的话，状

题意简述给你一棵\(n\)个节点以\(1\)为根的有根树，和一个整数\(m\)。对于树上每一个点\(u\)，有三个权值\(X,Y,Z\)。你需要在\(u\)的祖先里（不含\(u\)）中选出至少\(X\)个点，记\(S_1\)表示这些点到\(u\)的距离之和；在\(u\)的后代里（不含\(u\)）中选出至少\(Y\)个点，

设\(f(u,r)=\{v|dis(u,v)\ler\}\)，可以将其视作以\(u\)为圆心，\(r\)为半径的圆。有若干与欧几里得空间的圆相同的性质。设点集\(S\)的直径长度为\(d(S)\)，中点为\(m(S)\)，设\(c(S)=f(m(S),\dfrac{d(S)}{2})\)，可以视作\(S\)的最小覆盖圆。Lemma:若点集\(S

对于路径操作，DFS序是不可做的，可以考虑欧拉序欧拉序：对一棵树进行DFS，无论是第一次访问还是回溯，每次到达一个结点时都将编号记录下来，长度为2(n-1)+1=2n-1，每条边都被访问两次在LCA问题中，可以通过欧拉序将其转化为RMQ问题于是，[l,r]内DFS序最大的节点为路径的一个端点考虑记录下每