您现在的位置是:网站首页> 内容页

点分治略解

  • 大富豪登录网站
  • 2019-10-23
  • 215人已阅读
简介点分治被用来解决的问题:  给你一棵TREE,以及这棵树上边的距离。问有多少对点它们两者间的距离小于等于K。算法实现:先想想暴力做法吧,n3的,都会吧,暴力枚举两点,再暴力求出他们间的

点分治被用来解决的问题:

  给你一棵TREE,以及这棵树上边的距离。问有多少对点它们两者间的距离小于等于K。

算法实现:

先想想暴力做法吧,n3的,都会吧,暴力枚举两点,再暴力求出他们间的距离,判断是否小于k,统计答案。

nlog呢?很简单吧,就是把暴力求距离那一步改成LCA嘛。

那么我们的点分治就更加牛逼了,它可以在n log2 的时间内求解。

那么它是如何做到这么优秀的呢?我们来看看他的算法流程吧。

点分治主要是通过统计路径经过u的两个点(包括以u为路径的端点,其中这两个点是要在以u为根的子树中的),长度小于等于k的有多少,递归来求出最终的答案。

我们先讲讲如何统计路径经过u的两个点,长度小于等于k的有多少吧。

这应该很容易想的。

先一遍dfs求出从点u到以u为根的子树中各个点的距离。

那么我们把以u为根的子树中各个点到u的距离排序

排序之后,对于每一个点都二分匹配一个最大的和它相加小于等于k的另一个点,再统计答案。

但是我们发现,这么做会锅。

会遇到下图情况:

(手画的,有点难看,讲究一下下吧。。。)

假设k=8,当我们在做1号点时,我们会发现d[4]=4,d[5]=4,然后他俩就会牵手成功,然而这是错的,因为1-2的边被计算了两次。

这个时候呢,我们有两种解决方法:

1、注意到当这两个点不在u的同一个儿子时,便不会产生重复的路径,所以我们把各个点进行染色,把在u的同一个儿子中的点染成同一种颜色,然后不去匹配颜色相同的点就OK了。

2、利用融斥的思想,做以v(v为u的儿子)为根的子树,并把u中的各个节点到u的距离通通加上dist[u,v],在这种情况下依然能够牵手成功的两个点,就说明它是我们在上一次统计中出锅的情况,只要把这些情况减掉就可以了。

代码中我是用了第二种方法(毕竟比较简单嘛,代码也短)。

另一个问题——为什么一定要是在以u为根的子树中的点呢?还是直接看图吧:

也就是说此时的v2不在以u为根的子树中,那么就说明v1和v2被u到v2这段路径,辈分最高的那个点统计过了(就是图中从u连到骚粉矩形的边的另一个端点),不需要再次重复统计。

关于选择点的顺序以及时间复杂度的计算:

看了上述的算法流程,相比大家都会算时间复杂度吧。

T(n)=∑v∈u"s sons [T(siz[v])+Θ(n log n)]

很显然,时间复杂度和我们递归的层数是有关系的,那么我们选择点的顺序就很清楚了:

  为了让递归的层数尽可能的小,所以我们要每次选子树的重心开始做。

那么理论上时间复杂度最大的时候,就恰恰是一条链的时候,因为它会递归log n层,那么理论时间复杂度便是O(n log2)的了。

代码实现:

#include <bits/stdc++.h>using namespace std;const int maxn=40005,inf=100000000;int d[maxn],siz[maxn],f[maxn],head[maxn],nxt[maxn<<1],vet[maxn<<1],dist[maxn<<1];bool vis[maxn];int n,k,x,y,z,root,Siz,tot,cnt,ans;void add(int x,int y,int z){ nxt[++tot]=head[x]; vet[tot]=y; head[x]=tot; dist[tot]=z;}void getroot(int u,int father){ //找重心 siz[u]=1; f[u]=0; for (int i=head[u];i;i=nxt[i]){ int v=vet[i]; if (vis[v]||v==father) continue; getroot(v,u); f[u]=max(f[u],siz[v]); siz[u]+=siz[v]; } f[u]=max(f[u],Siz-siz[u]); if (f[u]<f[root]) root=u;}void getdis(int u,int father,int dis){ //求距离 d[++cnt]=dis; for (int i=head[u];i;i=nxt[i]){ int v=vet[i]; if (vis[v]||v==father) continue; getdis(v,u,dis+dist[i]); }}int find_right(int k,int left){ //求最大的能与now牵手成功的右端点 int l=left,r=cnt,ans=left; while (l<=r){ int mid=l+r>>1; if (d[mid]<=k) ans=mid,l=mid+1; else r=mid-1; } return ans;}int getans(int u,int dis){ //求答案 cnt=0; int res=0,now=1; getdis(u,0,dis); sort(d+1,d+1+cnt); while (now<cnt&&d[now]+d[cnt]<k) res+=cnt-now,now++; //说明全部都可以牵手成功 while (now<cnt&&d[now]+d[now+1]<=k){ int right=find_right(k-d[now],now+1); res+=right-now; now++; } return res;}void dfs(int u){ vis[u]=true; ans+=getans(u,0); for (int i=head[u];i;i=nxt[i]){ int v=vet[i]; if (vis[v]) continue; ans-=getans(v,dist[i]); //去掉上述在同一儿子中的情况 Siz=siz[v]; root=v; getroot(v,u); //确定下一个点 dfs(root); }}int main(){ scanf("%d",&n); for (int i=1;i<n;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } scanf("%d",&k); root=1; Siz=n; getroot(1,0); dfs(root); printf("%d",ans);}

文章评论

Top