\(dfs\)序
以\(DFS\)（先根遍历）⾸次访问顺序将节点重新排列。
特征：
- 每个顶点在序列中出现恰好⼀次（废话）
- ⽗节点排在⼦节点前⾯（废话）
- 每棵⼦树都占据序列的⼀个区间
欧拉序
记录\(DFS\)递归/回溯时依次经过的所有点。
特征：
- 每个点出现次数=度数（根多1次）
- 相邻点深度差1
- \(LCA(x,y)=\)区间[\(x\)⾸次出现, \(y\)⾸次出现]上深度最⼩的点
特征3，why?首先，一定经过\(lca\)（已经x->y）,1且lca上面的点一定不经过（回溯不会返回，怎么访问到y呢？）。 - 循环特征
II类欧拉序：
DFS序：递归u→v时，记v
欧拉序I：回溯u→p(u)时，额外记p(u)
欧拉序II：回溯u→p(u)时，额外记u
相当于进出⼦树u时，都各记录⼀次u
特征:
- 每个点u出现恰好2次，下标记为st[u]、ed[u]
- 直系路径x→y对应区间[st[x],st[y]]上只出现1次的点
我的感性理解：
DFS序擅长处理子树问题（它是区间）
欧拉序擅长处理各子树之间关系的问题，（各个子树清清楚楚）
II欧拉序擅长处理(非）直系路径的问题（路径清清楚楚）。
例题：
树上带修路径和问询。1887。
题意：有点权的树上,支持点更新,问询树上前缀和：\(S(u)=u\)到根节点的权值和。
\(Solution:\)
->直接维护点，暴力维护答案。
->既然维护点只能暴力维护答案，那我维护答案行不行？
→ u的点更新，会影响哪些节点的S？子树u（树上后缀）
→ DFS序上维护S数组点更新
→ S上的后缀更新前缀查询
→ S上的点查询
→ 线段树 或 差分+BIT
\(Another:\)
II类欧拉序。直系路径x→y对应区间[st[x],st[y]]上只出现1次的点。
从x→y，则⼦树x上
y的子树不会遍历到
侧链上的点都会被记录2次（1进1出）
只有路径上的点记录1次（1进0出）直系路径在欧拉序上为区间内只出现⼀次的点
→ 考虑路径上的⽬标函数
对应区间上，只要让出现2次的⽆贡献即可
→ st设权值系数*+1，ed设权值系数*-1
路径和=带权区间和，⽤BIT实现
→ ⽬标函数必须有可减性
有依赖的背包问题：
383。
从属关系形成了⼀棵树（加⼀个虚拟根）
选⼦节点必须先选择⽗节点
如不选节点u，其⼦树均不可选
→ 以DFS序后缀为状态状态：\(f[i][j] = dfn[i]≥i的物品放⼊空间j最⼤收益\)
本质后续探究。
换根子树大小问题：
给定⼀棵n个节点的⽆根树，有q个问询：求以X为根时，⼦树Y的节点数，
问询强制在线。n≤100000, q≤2000000
换根后。欧拉回路不变。（欧拉序循环）。
（相当于换了根）。
->子树仍然是个区间。
->区间是啥？\([x后第一次访问到y->最后一次访问到y]\)
转变为求不同值的个数。
->莫队可以，但过不去。
->考虑点对答案的贡献，只有欧拉序首次出现对答案有贡献。
→ 将欧拉序上⾸次出现的位置权值为1，其余为0
-> 求区间和就是⼦树大小。
dfs序就是没换根，直接分类讨论了。
离线非直系路径UV（II欧拉序）
\(Solution:\)
→ ⾮直系路径问询x→y
⽅法1：拆成x→lca和lca→y（需可加性）
⽅法2：对应区间[ed[x],st[y]]上
只出现1次的点，但LCA除外。UV没有可加/可减性怎么办。
->借助计数器，既然变成了区间出现一次点UV问题，可以莫队了。
->出现两次的点怎么维护？怎么知道该加还是该减？
->st+1，ed-1行不行？但是lca左侧ed，右侧st，显然完蛋。
->维护sgn(u)表示u出现次数%2
这样就o了。
直系路径和非直系路径对应区间不同！
BFS序
->无法转为连续区间，子树不连续。
->按bfs（层级顺序），这不就区间了。
区间加减查询，线段树，over.
→ 邻集N(u)=u及其所有相邻点（星型⼦图）
树上的邻集N(u)={u,p(u)} ∪ Son(u)
DFS/欧拉序上，Son(u)不是区间
→ BFS序上，Son(u)是区间
操作2,3：1~2次点更新 + 0~1次段更新
BFS序上建线段树，Over
混合序
各类序列化其本质思想是使树上节点尽量有序。
题意：
(有根）树上在线问询
操作1：\(将⼦树u中（以u为根的相对）深度≤k的点权+c\)
操作2：\(求⼦树u中深度≤k的权和\)
->bfs序交子树节点太多。
->dfs序是个区间，好处理。转变为求depth在一定区间内的点和。
->把点视为二维，二维线段树or二维差分前缀和，over
