终于在刷了半个寒假的计数题后学习了 (动态) 边分治, 写个博客记录一下.
然而做完两道题之后可能又不想管它了
以后再有练习的时候再更新吧.
用途
在 \(O(n\log n)\),\(O(n\log^2 n)\) 等复杂度内解决树上路径问题.
加了 "动态" 二字之后可以支持修改操作.
其实用途应该和点分治差不多.
实现
思路
类似于点分治, 我们选出一条中心边, 使两边的节点数尽可能平均, 作为该层的中心.
之后我们遍历左右子树得到左右子树的信息, 用某种方法合并, 得到跨越中心边的答案.
最后递归左右子树, 得到不过中心边的答案.
代码
先给个定义:
- #define go(x) for (int i=head[x];i;i=edge[i].nxt)
- #define v edge[i].t
- struct hh{int t,nxt,w;}edge[sz<<1],e[sz<<1]; // e: 原图; edge: 重构后的图
- int h[sz],head[sz],ec,ecnt=1;
- void M_E_(int f,int t,int w) // 本来想写 M_E, 然而这是保留字......
- {
- e[++ec]=(hh){t,h[f],w};
- h[f]=ec;
- e[++ec]=(hh){f,h[t],w};
- h[t]=ec;
- }
- void make_edge(int f,int t,int w)
- {
- edge[++ecnt]=(hh){t,head[f],w};
- head[f]=ecnt;
- edge[++ecnt]=(hh){f,head[t],w};
- head[t]=ecnt;
- }
首先, 有些图 (如菊花图) 不适合边分治. 我们需要加一些点和边, 使在答案不变的前提下构造出一个更善良的图.
- int cnt;
- void rebuild(int x,int fa)
- {
- int tmp=0;
- for (int i=h[x];i;i=e[i].nxt)
- {
- int v=e[i].t,w=e[i].w;
- if (v==fa) continue;
- if (!tmp) make_edge(x,v,w),tmp=x;
- else
- {
- int t=++cnt;
- make_edge(tmp,t,0);
- make_edge(t,v,w);
- tmp=t;
- }
- rebuild(v,x);
- }
- }
然后是找中心边:
- bool del[sz]; // 是否已经分治过
- int ct,ctS,sum; // 中心边, 最小 size, 总大小
- int size[sz]; // 子树大小
- void calcS(int x,int fa)
- {
- size[x]=1;
- go(x) if (v!=fa&&!del[i>>1])
- {
- calcS(v,x);
- size[x]+=size[v];
- }
- }
- void findct(int x,int fa)
- {
- go(x) if (v!=fa&&!del[i>>1])
- {
- findct(v,x);
- int S=max(size[v],sum-size[v]);
- if (chkmin(ctS,S)) ct=i;
- }
- }
接着是遍历左右子树:
- int dis[sz],s[sz];
- void calcDis(int x,int fa,int d,int side)
- {
- dis[x]=d;s[x]=side;
- go(x) if (!del[i>>1]&&v!=fa) calcDis(v,x,d+edge[i].w,side);
- }
最后是分治:
- int divide(int x)
- {
- calcS(x,0);
- ct=-1;ctS=1e9;sum=size[x];
- findct(x,0);
- if (ct==-1) return ...;
- int l=edge[ct].t,r=edge[ct^1].t;
- del[ct>>1]=1;
- calcDis(l,0,0,0);calcDis(r,0,0,1);
- int ret=-1e9;
- //do something ......
- ret=max(ret,max(divide(l),divide(r)));
- return ret;
- }
没了.
拓展
这东西是可以支持修改操作的.
对于每个原树中的点, 记录它在哪些中心边的子树内, 左子树还是右子树, 它对这条中心边的贡献是什么.
对于每一条中心边, 维护一些数据结构存储左右子树的信息.
修改一个点时就从下至上维护中心边的信息即可.
例题: 洛谷 P2056 [ZJOI2007]捉迷藏
例题
我做题少不敢瞎 BB\(Q\omega Q\)
以后更新吧......
(动态)边分治学习笔记
来源: http://www.bubuko.com/infodetail-2947692.html