DFS序列

考虑 这样一棵树，5个点，4条边，根节点是1

1 2
1 3
3 4
3 5

DFS序有两种
进出栈序

1 2 2 3 4 4 5 5 3 1

欧拉序

1 2 1 3 4 3 5 3

欧拉序

欧拉序，每个点被访问一次，就会被记录一次

1 2 1 3 4 3 5 3

总长度$2n-2$
每个点出现次数 等于 自己的度数
两个点的LCA，就是两个点之间最浅的点

进出栈序

+表示进栈，-表示出栈

1 2 2 3 4 4 5 5 3 1
+ + - + + - + - - -

每个数字恰好出现$2$次

在一些实现中，我们只存第一次出现

单点修改，查询子树之和

子树是区间
只在每个点的第一次出现加上点权

单点修改，查询一个点到根节点路径之和

这个点的第一次出现加上点权
这个点的第二次出现减去点权
查询前缀即可