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) 的查询所有节点的权值了。

分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注