点分治学习笔记

什么是点分治?

点分治就是一种解决树上问题的分治算法。每次分治的时候找到树的重心作为新根解决问题,然后根去掉,分治剩下的联通块。

getroot

找树的重心的函数

树的重心就是使树最均衡的那个点(感性理解一下),也就是将它为根抖落抖落,最大的子树最小的那个点,所以只要对于每个点求一下最大子树大小就好啦

并没有必要把所有的点搞成根,根为$x$的父亲的子树的大小只要用总的大小减去以$x$为根的子树的大小即可求出

void getroot(Node *x, Node *fa){
	x->siz=1, x->mx=0;
        //x->siz记录原树中以x为根的子树的大小
        //x->mx记录以x为根的树中x的最大子树的大小
	for(Edge *i=x->head; i; i=i->ne){
		if(i->to->vis || i->to==fa)	continue;
		getroot(i->to, x);
		x->siz+=i->to->siz;
		x->mx=max(x->mx, i->to->siz);
	}
	x->mx=max(x->mx, SumSiz-x->siz);
        //记录一下 原树中x的父亲为根的 子树的大小
	root=root ? (x->mx<root->mx ? x : root) : x;
}

divide

不断重复找重心,标记重心已使用,递归进入子联通块的过程

solve函数为一个统计答案的函数

void divide(Node *x){
    ans+=solve(x, 0);
    x->vis=true;
    for(Edge *i=x->head; i; i=i->ne){
        if(i->to->vis)	continue;
        ans-=solve(i->to, i->val);
        SumSiz=i->to->siz, root=NULL;
        getroot(i->to, NULL);    //求新联通块的重心
        divide(root);            //递归求解
    }
}

入门题

做完入门题(伪)的入门套路总结

一般有两种方法,一种是两次dfs计算,比如[Luogu P3806] 【模板】点分治1[Luogu P4149] [IOI2011]Race;另一种是运用小学二年级奥数难度的容斥原理,比如[Luogu P4178] Tree[Luogu P2634] [国家集训队]聪聪可可

发表评论

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