1. 用途

首先是有根树。
我们需要实现如从点 u 到点 v 的（最短）路径上所有点的权值+1 这种操作。
而且我们不需要频繁的求某个点的权值。

2. 实现方法

类似于前缀和的思想。
首先我们定义：val[i] 表示点 i 的标记，cal[i] 表示点 i 的权值，lca(i,j) 表示点 i 与点 j 的最近公共祖先，fa[i] 表示点 i 的父亲节点（等于 0 表示没有父亲节点）。

先看操作：
点 u 到点 v 之间的路径上每个点的权值+1：

void change(int u,int v)
{
    val[u]++,val[v]++,val[lca(u,v)]--;
    if(fa[lca(u,v)])val[fa[lca(u,v)]]--;
}

求点 a 的权值：

void calc(int a)
{
    cal[a]=val[a];
    for(枚举点 a 的儿子 i)calc(i),cal[a]+=cal[i];
}

注意 cal[i] 并不是时时刻刻一定等于点 i 的权值，而是你 calc(i) 后才一定是正确的值。

上面的操作为什么是这样的呢？首先不难发现 cal[a] 就是 a 所有的儿子节点和 a 的 val 的和，因为其实 val[i]++等价于将点 i 到根节点的所有点的权值都加了 1, 所以 change 函数中先将 val[u]++,val[v]++，这样 lca(u,v) 的权值本应该只加 1，现在却加了两次，所以 val[lca(u,v)]–。而 fa[lca(u,v)] 本来权值不应增加，而此时权值却加了 2, 所以应该减去 2，但是因为 lca(u,v) 的权值已经减一了，所以 val[fa[lca(u,v)]] 只需要减一即可。

这样就实现了 O(1) 的修改，O(n) 的查询所有节点的权值了。