Download presentation
Presentation is loading. Please wait.
1
支配树 河南省实验中学 王梦迪
2
膜拜&吐槽 CodeChef DAGCH 红杏枝头春意闹，膜拜神犇lcy
3
HDOJ 4694 Important Sisters
有N<=5*10^4个炮姐，之间存在单向的信息传递关系，构成一张M<=10^5的有向图 炮姐N是所有消息的源头 如果去掉炮姐b，炮姐N就无法给炮姐a传递信息，则称b是a的important sister 求每个炮姐的所有important sister的编号之和
4
HDOJ 4694 Important Sisters
暴力？O(N^2*(N+M)) 我们需要一个更加优美的算法 PPT的主题就是这个算法
5
支配 有向图，固定起点r 若r~w的每一条路径都必定经过v≠w，则v支配w r v w
6
最近支配点 若v支配w，且w的其余支配点全都支配v，则称v是w的最近支配点，v=idom(w)
v=idom(w), b=idom(v), a=idom(b), r=idom(a) r a b v w
7
定理1（支配树定理） 除r外都有唯一idom，且不成环，故所有(idom(w),w)形成一棵树，v支配w当且仅当v是树中w的祖先，这棵树叫支配树 r
8
求解支配树 Important Sisters这道题就是求解每个点在支配树上所有祖先的编号之和 只要求出支配树，题目就迎刃而解了
Lengauer_Tarjan算法：O(N*α(N))求出所有点的最近支配点，以及半支配点（见后面） 读作：兰高娃-塔儿尖算法
9
引理1（路径引理） 从r开始DFS整张图，按DFS序给结点重编号 （以后r就是1了）
若v<=w，则v~w的任意路径都包含它们在T中的一个公共祖先 证明：横叉边只从大到小 3 如果不经过公共祖先，就意味着必然有一条回边，其终点编号大于起点，而这是不被允许的 2 4 r 5 6
10
半支配点 sdom(w)=min{v|有一条路径v=v0, v1, …, vk=w，使得vi>w对1<=i<=k-1成立}
r sw w
11
图论预警 一坨关于idom和sdom的性质 （然而并不难） 有问题请务必指出
若无特殊声明，以下缩写sa=sdom(a)，ia=idom(a)
12
引理2 idom(w) +-> w “+->”：idom(w)是w在T中的祖先，且idom(w)≠w
证明：既然idom(w)在每一条r~w路径上，那就必然在这一条树路径上 w r w
13
引理3 sdom(w) +-> w（以下sdom(w)简称sw）
证明：由定义，sw<=father(w)<w，由引理1，路径sw, v1, …, vk=w中某个点是sw和w的公共祖先，那么这个点只能是v0=sw sw在粗箭头上 r ? w
14
引理4 idom(w)··->sdom(w) “··->”：idom(w)是sdom(w)在T中的祖先，有可能等于sdom(w)
r sw ? w
15
引理5 若v··->w 则v··->idom(w)或idom(w)··->idom(v) （不可能在红色段）
证明：否则设为x，由于r~v可以不经过x，所以r~w可以不经过x，和x支配w矛盾 r iv ? v w
16
图论高能预警 终于该讲怎么求了！ 撒花！ 接下来的定理2、3描述如何用sdom求idom，定理4描述如何求sdom
17
定理2 若所有使得sdom(w)+->u··->w的u都满足sdom(u)>=sdom(w)
则idom(w)=sdom(w) r sw su u w
18
定理2 证明：由引理4，只需证sdom(w)支配了w 考虑r~w任意一条路径p，上面最后一个小于sdom(w)的点x
（若没有，则sdom(w)=r支配w） 设y是路径上x之后首个sdom(w)··->y··->w的点 x~y的路径是x=v0,v1,v2,…,vk=y v2 v1 x Vk-1 r sw y w
19
定理2 断言：vi<y对1<=i<=k-1成立 证明：否则某个vi<y，由引理1，有j>=i满足vj是y的祖先
由于x的选法，vj>=sdom(w) 则sdom(w)··->vj··->y··->w和y的选法矛盾 vi x r sw vj y w
20
定理2 从v1开始一直>y，x满足sdom(y)定义式中条件
由断言，sdom(y)<=x<sdom(w)，由本定理的假设，y不是sdom(w)的完全后代，必有y=sdom(w) v1 x Vk-1 r sw y w
21
定理2 所以sdom(w)=y在任意路径p上均出现 sdom(w)必然支配w 这足以证明sdom(w)=idom(w)，证毕■ x r
sw=y w
22
定理3 设u是所有sdom(w)+->u··->w的节点中sdom(u)最小者 则idom(u)=idom(w)
23
定理3 证明： 由引理5，idom(w)不在红色段，即要么idom(w)··->idom(u)，要么u··->idom(w)
由引理4，idom(w)··->sdom(w)+->u 只能idom(w)··->idom(u) r iw iu u w
24
定理3 为证明idom(u)=idom(w)，只需证明idom(u)支配w
考虑r~w的任意路径p上最后一个<idom(u)的点x（若没有，则idom(u)=r支配w） 设y是路径上x之后首个idom(u)··->y··->w的点 x~y的路径是x=v0,v1,v2,…,vk-1,vk=y v2 v1 x Vk-1 r iu y w
25
定理3 和定理2类似，vi>y对1<=i<=k-1成立，sdom(y)<=x<idom(u)
断言：y不可能是idom(u)的完全后代 证明：否则存在一条r~sdom(y)~y~u的路径避开idom(u)，和idom(u)支配u矛盾 r sy iu y sw u w
26
定理3 根据y的选法，idom(u)··->y··->w 根据断言，y不是idom(u)的完全后代 所以y=idom(u)
idom(u)在任意路径p上 Idom(u)支配w，证毕■
27
推论1 回顾一下，我们干啥来了？ 当然是求idom！ 综合定理2,3，可以由sdom求出idom
设u是满足sdom(w)+->u··->w的u中sdom(u)最小者 若sdom(u)=sdom(w)，则idom(w)=sdom(w) 否则，idom(w)=idom(u)
28
然而 sdom怎么求啊？
29
定理4 sdom(w)=min{ } {v|(v,w)∈E且v<w} ∪
{sdom(u)|u>w且有边(v,w)满足u··->v} }
30
定理4·第一种 v r w
31
定理4·第二种 r w su u v
32
定理4 证明： 设等式右端为x 先证sdom(w)<=x 再证sdom(w)>=x
33
定理4·sdom(w)<=x 若x<w且(x,w)∈E（第一种） 否则，若x=sdom(u)，u>w（第二种）
则x满足sdom(w)的定义式，sdom(w)<=x 否则，若x=sdom(u)，u>w（第二种） 则存在一条x~u-v~w的路径，其中x~u段除头尾， 始终保持>u x亦满足sdom(w)的定义式，sdom(w)<=x
34
定理4·sdom(w)<=x 注意白实线路径 w r su u v
35
定理4·sdom(w)>=x 设简单路径：sdom(w)=v0, v1, …, vk=w，满足vi>w对1<=i<=k-1成立 若k=1，则(sdom(w),w)∈E，sdom(w)满足x的定义式，必有x<=sdom(w) 否则，设vj是路径上v1之后，首个满足条件vj··->vk-1的 j一定存在，因为j可以是k-1 j是：j>=1且vj··->vk-1的最小值
36
定理4·sdom(w)>=x 仿照定理2,3的证明，vi>vj对1<=i<=j-1成立
故sdom(w)满足sdom(vj)的定义式 sdom(vj)<=sdom(w) sdom(vj)又满足x的定义式（第二种） 故x<=sdom(vj)<=sdom(w) v1 vj vk-1 r sw w
37
定理4 综上，x<=sdom(w)<=x 必有sdom(w)=x 证毕■
38
证完了 撒花！
39
实现 可以做到O(N*α(N)) 并查集维护“某点到链顶端的最大值” 先倒序求所有sdom 再倒序求推论1中的u 再顺序求idom 详见标程
40
两道CodeChef例题 GRAPHCNT DAGCH
给一张有向图。求有多少个点对(x,y)，使得存在 1~x和1~y的两条不相交（除了1）路径。 N<=10^5,M<=5*10^5. 求出支配树中1的每棵子树大小即可 DAGCH 求每个点的半支配点，N<=10^5,M<=2*10^5 裸题
41
参考资料 Tarjan原论文： 翻译（部分）：
42
谢谢大家
Similar presentations
