Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

[算法xio讲堂#3]点分治

chhokmah 2019-02-25 13:24:00 阅读数:175 评论数:0 点赞数:0 收藏数:0

点分治

感觉点分治不怎么难可能是我太弱了,算了。不BB了。


定义

所谓点分治,就是基于点来做分治。而分治是分而治之的意思,比如说我们有一群范围非常大的的问题,但是这些问题都有一些相似的特性,那么我们就按照这个特性来分掉这些问题,然后对于每一个问题都按照相似的处理方式,得到最小的答案,然后将小的答案按照某种方式算出整个问题的答案。像这种求解的方法就叫做分治。

其实沃认为点分治更像是一种高级暴力(逃跑)

回归正题,那么在一棵树上也是同一个道理,将一棵树分成一棵棵的小树,然后对每一棵树进行操作。

那么像这种方法求解树上的问题,一般都能至少降低一个\(log\)级别的复杂度,但是更多的都是将复杂度从\(O(n^3)\)降到\(O(n^2)\),这样我们的程序就会避免遍历一些重复的状态,从而减少运算的次数。


原理(基于重心的分割)

首先点分治作为一种高效搞笑算法,需要全面的考虑任何的退化情况。对于树上的特殊情况有三种:菊花图,链,和菊花链,这三种情况最有可能会让树上的算法退化时间复杂度。

但是对于点分治来说还是链的影响更大一点,那么我们想一下如何将分治掉这条链。

非常明显,将这条链二分比较的好,但是对于一般的问题我们又应该怎么平均分呢?

这个时候我们引入一个新的概念叫做重心

所谓重心,就是在这棵树中最重的地方,准确的定义是:最大的子树后辈节点个数最少的节点叫做重心。

为什么要引入这个概念,因为树的重心能把一棵树尽可能地平均分配。

\(ps.\)重心有一个比较神奇的性质:每一个子树的大小都不超过n/2

关于重心性质的证明

考虑有如上这么一棵树,其中\(u\)是重心,\(son[u]\)表示\(u\)点的最大的子树的大小,\(v\)是点\(u\)的最大子树,且\(size[v]>\frac{size[u]}{2}\)

因为\(size[v]>\frac{size[u]}{2}\),其他子树加上点\(u\)的节点数小于\(\frac{size[u]}{2}\),那么不难发现,我们选择点\(v\)作为重心,\(son[v]=size[v]−1<son[u]\),那么很明显\(u\)不满足重心的定义。


举一个例子:((●'◡'●))

像这棵树的重心就是\(4\)号点,这棵树中\(4\)号点最大子树后辈节点个数为\(11\),是整棵树上的所有节点中最小。也说明了这个节点能尽可能平均地分割这棵树。

求解重心的代码

void getroot(int u,int fa){
sz[u]=1; mxs[u]=0;//sz数组是子树的节点个数,mxs是maxson的缩写,表示的是最大的子树的节点数
for(int e=H[u];e;e=E[e].nt){//前向星的遍历方式
int v=E[e].to;
if (v==fa) continue;//如果遇到了父亲那么就跳过
getroot(v,u);//向下递归求解
sz[u]+=sz[v];
mxs[u]=max(mxs[u],sz[v]);//计算mxs
}
mxs[u]=max(mxs[u],sum-sz[u]);//这是另外一半的树,这也是这棵树的子树(整棵树被当作了无根树)
if(mxs[u]<mxs[rt]||rt==0) rt=u;//判断是不是重心
}

有位大佬的博客上写了一些不同的看法:传送门


“分而治之”的“治”操作

这个比较难讲清楚,我尝试一点一点来将问题讲清楚。

我先贴出一个伪代码,让大家了解一下

void divide
计算当前全局的答案
记录访问节点
枚举子节点{
如果访问过就跳过
将局部重复解减去
递归搜索子树重心
}

首先对于点分治的答案计算需要一点容斥原理的知识,我们以某谷的模板题为例:传送门

void solve(int u){
calc(u,1,0);//计算答案
vis[u]=1;//标记已经访问过了
for(int e=H[u];e;e=E[e].nt){
int v=E[e].to;
if(vis[v]) continue;//如果已经访问过了就不用访问了,也起到了不算父亲的情况
calc(v,0,E[e].w);//容斥原理减去所有重复的状态
MX=inf; sum=sz[v]; rt=0; getroot(v,-1);//算出子树的重心
solve(rt);//递归求解
}
}

第一次看到别人blog的时候,我也是非常懵逼的?但是理解起来还是比较简单的,其核心是容斥原理:在扯一点题外话:所谓容斥原理就是在计算问题是有重复的部分,我们先将所有的部分全部都算出来,这样在将多出来的重复部分减去,保证答案的正确性。

那么对于树上点分治有什么需要容斥原理的地方,很明显:假设我们要计算的答案是\(ans1=getans(rt->u->v1)\),那么也会算出\(ans2=getans(rt->u->v2)\),其中的\(v1\)\(v2\)都是\(u\)的儿子,因为要保证答案的正确性,那么我们一定是要将\(ans1\)\(ans2\)加起来,或者是其他的整合操作,但是这个时候我们需要考虑一个问题,整合时候\(rt->u\)这一部分的答案是不是算了两边,也就是容斥原理中所说的重复部分。有人会问:为什么会重复?这个不是树上的操作?不是一般都不会有重复的吗?不然\(dfs\)暴力求解怎么做?有人这样问我。请在看一下我们的程序框架,我们是算出答案后在计算分治求解接下去的答案。

那么为什么不能先递归下层节点,在计算答案?因为下层的答案是由上层的答案求出的,这和其他的树上操作有一点不一样,不然求出的答案就会只有部分解。

那么回归正题,我们来举一个例子更生动地理解一下,再次清楚我们的的图片君,(●'◡'●)

假设假设假设(先不管重心君),我们求\(1-2-4\)的答案,那么是不是又要求解\(1-2-5\)的答案,那么将两个答案整合后,就hi将\(1-2\)这一部分的答案计算两遍,那么我们就要减去这个重复的部分。

\(Chhokmah\)(叹了一口气):终于差不多讲完了,接下来就是题目。。。


习题

洛谷模板3806

题目描述

给定一棵有n个点的树,询问树上距离为k的点对是否存在。

解法

一次分治就将所有的答案都算出来,这也是可以做到的。
上文已经讲的非常清楚了。

ac代码

#include<bits/stdc++.h>
#define N 100005
#define inf 0x3f3f3f3f
using namespace std;
struct edge{
int to,nt,w;
}E[N<<1];
int H[N],ans[10000005],sz[N],mxs[N],S,vis[N],dis[N];
int n,m,sum,cnt,tot,rt,MX;
int read(){
int w=0,x=0;char ch=0;
while(!isdigit(ch))w|=ch=='-',ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return w?-x:x;
}
void addedge(int u,int v,int w){
E[++cnt]=(edge){v,H[u],w}; H[u]=cnt;
}
void getroot(int u,int fa){
sz[u]=1; mxs[u]=0;
for(int e=H[u];e;e=E[e].nt){
int v=E[e].to;
if (v==fa||vis[v]) continue;
getroot(v,u);
sz[u]+=sz[v];
mxs[u]=max(mxs[u],sz[v]);
}
mxs[u]=max(mxs[u],sum-sz[u]);
if(mxs[u]<MX) rt=u,MX=mxs[u];
}
void getdis(int u,int fa,int dist){
dis[++tot]=dist;
for(int e=H[u];e;e=E[e].nt){
int v=E[e].to;
if(v==fa||vis[v]) continue;
getdis(v,u,dist+E[e].w);
}
}
void calc(int u,int fg,int len){
tot=0;
getdis(u,-1,len);
for(int i=1;i<tot;i++){
for(int j=i+1;j<=tot;j++){
if(fg) ans[dis[i]+dis[j]]++;
else ans[dis[i]+dis[j]]--;
}
}
}
void solve(int u){
calc(u,1,0);
vis[u]=1;
for(int e=H[u];e;e=E[e].nt){
int v=E[e].to;
if(vis[v]) continue;
calc(v,0,E[e].w);
MX=inf; sum=sz[v]; rt=0; getroot(v,-1);
solve(rt);
}
}
int main(){
n=read(),m=read();
for(int i=1;i<n;i++){
int u=read(),v=read(),w=read();
addedge(u,v,w);
addedge(v,u,w);
}
sum=n; MX=inf;
getroot(1,-1);
solve(rt);
while(m--){
int k=read();
if(ans[k]>0) printf("AYE\n"); else printf("NAY\n");
}
return 0;
}

[poj1741]Tree

题目描述

Give a tree with n vertices,each edge has a length(positive integer less than 1001).
Define dist(u,v)=The min distance between node u and v.
Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.
Write a program that will count how many pairs which are valid for a given tree.

题目大意

给一棵边带权树,问两点之间的距离小于等于K的点对有多少个。

解法

暴力就是枚举点对,计算距离,但是一定T。

我们就可以用点分治来解决这道题。

如果我们已经知道了此时所有点到根的距离a[i],a[x] + a[y] <= k的(x, y)对数就是结果,这个可以通过排序之后O(n)的复杂度求出。然后根据分治的思想,分别对所有的儿子求一遍即可,但是这会出现重复的——当前情况下两个点位于一颗子树中,那么应该将其减掉(显然这两个点是满足题意的,为什么减掉呢?因为在对子树进行求解的时候,会重新计算)。

在进行分治时,为了避免树退化成一条链而导致时间复杂度变为O(N^2),每次都找树的重心,这样,所有的子树规模就会变的很小了。时间复杂度O(Nlog^2N)。

ac代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;
int read(){
int w=0,x=0;char ch=0;
while(!isdigit(ch))w|=ch=='-',ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return w?-x:x;
}
int n,K,cnt,sum,ans,root;
int head[10005],deep[10005],d[10005],f[10005],son[10005];
bool vis[10005];
struct data{int to,next,v;}e[20005];
void ins(int u,int v,int w)
{e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=w;}
void insert(int u,int v,int w)
{ins(u,v,w);ins(v,u,w);}
void getroot(int x,int fa)
{
son[x]=1;f[x]=0;
for(int i=head[x];i;i=e[i].next)
{
if(e[i].to==fa||vis[e[i].to])continue;
getroot(e[i].to,x);
son[x]+=son[e[i].to];
f[x]=max(f[x],son[e[i].to]);
}
f[x]=max(f[x],sum-son[x]);
if(f[x]<f[root])root=x;
}
void getdeep(int x,int fa)
{
deep[++deep[0]]=d[x];
for(int i=head[x];i;i=e[i].next)
{
if(e[i].to==fa||vis[e[i].to])continue;
d[e[i].to]=d[x]+e[i].v;
getdeep(e[i].to,x);
}
}
int cal(int x,int now)
{
d[x]=now;deep[0]=0;
getdeep(x,0);
sort(deep+1,deep+deep[0]+1);
int t=0,l,r;
for(l=1,r=deep[0];l<r;)
{
if(deep[l]+deep[r]<=K){t+=r-l;l++;}
else r--;
}
return t;
}
void work(int x)
{
ans+=cal(x,0);
vis[x]=1;
for(int i=head[x];i;i=e[i].next)
{
if(vis[e[i].to])continue;
ans-=cal(e[i].to,e[i].v);
sum=son[e[i].to];
root=0;
getroot(e[i].to,root);
work(root);
}
}
int main()
{
while(1)
{
ans=0;root=0;cnt=0;
memset(vis,0,sizeof(vis));
memset(head,0,sizeof(head));
n=read();K=read();
if(n==0)break;
for(int i=1;i<n;i++)
{
int u=read(),v=read(),w=read();
insert(u,v,w);
}
sum=n;f[0]=inf;
getroot(1,0);
work(root);
printf("%d\n",ans);
}
return 0;
}
版权声明
本文为[chhokmah]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/chhokmah/p/10430418.html

编程之旅,人生之路,不止于编程,还有诗和远方。
阅代码原理,看框架知识,学企业实践;
赏诗词,读日记,踏人生之路,观世界之行;

支付宝红包,每日可领