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

发表评论

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

你是机器人吗? =。= *