Any questions?
Reply Back New Topic
View Topic

2427: Appletree【题解】【搬运】

2427 浏览:959 回复:2 赞:28 Started by Tanbowen 2 months ago

回想倍增法求LCA的过程

从大到小枚举k,每次跳2^k步,只要不越界就跳,最后一定能跳到LCA

因为跳的都是2的幂次步,所以每跳一步就是二进制加了一个1

先预处理fai,表示点i向上跳2^k 步的祖先节点

设 fi 表示最后一步跳了2^j步,跳到了点i的答案之和

cnti 表示最后一步跳了2^j步,跳到了点i的方案数

因为有了倍增求lCA原理的保证,所以只需要考虑跳2的幂次步

设siz[i]表示以i为根的子树的大小

rt[i]=j 表示 当前点属于 i的子树里,以j为根节点的子树

假设dfs回溯到x,转移分两种:

1、以x为链的一个端点

枚举x向上跳2^k次,则v=fax

那么ans+=siz[v]-siz[rt[v]] ——所有非rt[v]子树的点,与x的LCA都是v,都会有1的贡献

(类似于点分治中要去除同一子树内合法的点)

cntv++ fv++

2、x作为倍增过程中的一个中途点

那么枚举最后一步跳了 2^i 跳到了x

枚举x再往上跳2^j步,则v=fax

那么ans+=(fx+cntx)*(siz[v]-siz[rt[v]])

fx 是原来的答案,在以v做LCA时,又会用 (siz[v]-siz[rt[v]])次

cntx 是 要再往上跳2^j步,又有一个1的贡献

cntv+=cntx fv+=fx+cntx

例:1--2--3--4 如果4到1的距离为3,二进制为11,对答案的贡献为2

回溯到4的时候,以4为端点会累积3--4 2--4

回溯到3的时候,以3为端点会累积2--3 1--3

回溯到2的时候,以2为端点会累积1--2,以2为中途点会累积1--2--3--4

(4跳2^1累积到2里,然后在枚举2为中途点时,最后一步跳了2^1到2,2再往上跳2^0)

为什么在枚举3作为中途点的时候,不枚举跳了2^0次方到了3

因为此时3不是中途点,我们是按跳2^k,k是降序跳的

个人总结:支持本题不重不漏的原理就是倍增求LCA的原理

或者是说任意数可以拆为2^k1+2^k2+2^k3…… ki 依次递减

——————————————————————————————————————————————————————————————————————————

转自:https://www.cnblogs.com/TheRoadToTheGold/p/7655156

View Replies

Replied by null 2 weeks ago 赞:2

ด้้้้็็็็็้้้้้็็็็็้้้้้้้้็็็็็้้้้้็็็็็้


Replied by null 2 weeks ago 赞:2

被机惨。