题意简述给你一棵\(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序最大的节点为路径的一个端点考虑记录下每

题意：维护一棵树，某些点有点权（没有则为正无穷），点权为正整数，查询树上路径点权小于等于某个值的点的个数。分析:考虑维护主席树，root[i]数组存储第i个节点到根的点权的权值线段树的树根。更具体地，把第i个节点到根的路径上的点权累积到权值线段树中，对一个询问x,y，记lca为z,查询值为k，答案a

第2题   树上游戏 查看测评数据信息有一棵n个节点的树。T站在u号节点上，A站在v号节点上。现在，两个人轮流移动，T是先手。每人每次移动必须移动到任何一个相邻的节点。如果某个人发现自己与对方站在了同一个节点上，那么宣布游戏结束。注意每个人每一轮必须移动。已知T希望游戏

lg树上操作P3258树上差分P1600[NOIP2016]天天爱跑步分开两边处理。对于上升段，如果一个点深度是x=dep_i+w_i，那么i就被贡献我们可以将整个上升段的x位置都加，然后在每个点处统计dep_i+w_i位置的值。每个点开一个vector记录修改操作。不过这样可能会有互相影响

启发式合并（set）元素少的set中的元素一一插入元素多的set中。时间两只\(\log\)。空间最坏为\(n\)这个级别（结点数）（这是在默认一个结点最多增加一个元素的情况下）。log数据结构时间也是两只\(\log\)。dsuontree好像[也叫“树上启发式合并”]（？？）。[一般]（？）是重链剖分一样划分

bfs序dfs序可以用来维护子树内的信息，而bfs序可以用来树上相同层数之间的信息。性质：\(bfs\)序上\(y\)离\(x\)越近，\(lca(x,y)\)深度约大。所以可以使用二分，找到与\(x\)在某同一子树的\(y\)。树上合并问题：长链剖分+合并：可以解决与\(dep\)有关的树上合并问题。时间复杂度\(O(n

树上莫队通过将树转化成DFS序（欧拉序）来解决问题。这道题目跟“HH的项链”很像，考虑树上莫队首先对树做出一个欧拉序，得到每个点在欧拉序中第一次出现的位置in[x]和第二次出现的位置out[x]；如果某个询问的\((x,y)\)的in[x]比in[y]大，那么交换\(x,y\)，下面假设in[x]比in[y]小如果\(x,y\)

欢迎来看“片”（的简介）由于-\(看片\)-生涯转瞬即逝，于是我选择对“\(片\)”进行一定的总结：相信你一定看懂了由于开始的时间有一点晚，就姑且认为我以后会慢慢补充吧......回到总部点分治\(P4178\)\(Tree\)解：树的重心，树上\(DFS\)搜索，点分治经过（两）天(一)夜的鏖战，总算\(\m

题意：给\(p\)和\(p-1\)个边权，要用这些边权构造树，每个点编号\(0\simp-1\)，使得每个点\(u\)到\(0\)的距离\(\bmod\p=u\)，无解输出-1，保证\(p\)是质数、\(p\le10^6\)、边权\(\in[1..p-1]\).Solution考虑加边的过程，树最开始只有根节点0，然后通过加边不断地引入新的点

因为我需要去天津和高二大佬集训，所以试图复活我的OI有好多需要复习的模板啊感觉，各位能不能提点建议莫队回滚【待完成】带修【待完成】二次离线【待完成】树上【待完成】二维【待完成】数据结构线段树【待完成】合并【待完成】动态开点【待完成】

lcalca简称最近公共祖先——简介在此，不过多赘述这里主要写的是倍增算法，oi-wiki上用的是vector，由于本人不会，只会用链表，所以这里就放链表的代码了例题加一个数组按倍增数组的方式存距离即可题解——点击查看代码#include<bits/stdc++.h>#defineintlonglongconstint

D.网络攻防题意：一张无向图，求至多删除\(k\)条边使得图不连通的方案数。\(k\in[1,2]\)。首先考虑\(k=1\)，答案即为无向图中的桥边。预计得分\(15\)分。对于\(m\le2\times10^3\)的数据，我们可以枚举一条边删除，求剩余图中的桥边数量，最后加上桥边数量即可。预计得分\(30\)

树上启发式合并（DSUontree），和莫队一样都是暴力美学，用于解决一些树上离线问题，尤其是指“对于每个节点，询问关于子树的信息”这类问题。而且虽然是暴力做法，但是时间复杂度神奇的来到了\(O(nlogn)\)。启发式合并启发式合并是一种思想，在合并两个集合时，优先将小集合合并到大集合中去

P4606[SDOI2018]战略游戏狗屎虚树+圆方树。顺便第一次打欧拉序求LCA。注意特判根节点的情况即可，甚至不需要dp。P4334[COI2007]Policijasblhy直接给我交题解了，那我就不打了。说一个最重要的点：如何判断树上\(z\)在\(x,y\)的简单路径上？dfn序：满足两个条件。