POJ 1741 点分治

这是一道非常经典的点分治的题目。传说楼教主自己捣鼓出了点分治这种方法,出给大家做。对于点分治、边分治、路径剖分这类树上的分治策略,参考漆子超在2009年写过的一篇论文。

漆子超《分治算法在树的路径问题中的应用》

里边讲的树剖,到现在对我来说还是过不去的坎!为了调试SPOJ QTREE,花费了我一整天的时间却怎么样都WA!不过这篇文章主要是讲点分治和边分治,还是不要跑题了。

点分治

我们要找一些路径满足某个条件。路径总数是O(n2)级别的,直接枚举,就算其他的过程是常数级别的,时间复杂度也已经达到了O(n2)级别,显然会超时。为了优化,我们考虑分治策略。

首先把一棵无根树转换成有根树。这句话的意思是,随便找个点当作根,因为只有n-1条边n个点的连通图怎样都是一棵树。稍后我们将会看到选择这个点是有策略的。

将路径分为两类:

  1. 经过根节点的
  2. 不经过根节点的

这样考虑问题会不会简单一点呢?看看上面的POJ1741,先从根节点遍历所有节点,得到每个节点到根节点的距离,就很容易得到两两距离了。统计有多少点对满足条件,需要对所有的节点到根节点的路径长度排个序,之后用两个指针,一个从前面开始扫,一个从后面退回来,很容易就能统计出有多少点对的路径长度小于等于k。当然要减去没有经过根节点的而且满足条件的点对数量,这个可以在每一颗子树遍历完之后类似地求出来。这个的具体实现请看程序。

递归实现

刚刚讨论完了经过根节点的情况,没有经过根结点的情况其实是一样处理的。对于每一颗子树,都还是树嘛,所以转化成了子问题,而且这个问题和大的问题没有重叠,也没有遗漏,只要在遍历完每个子树之后都进行打标记,当过根节点的不能再参加计算就可以了。

效率分析

我刚刚看到这个做法的时候,一不小心把时间复杂度算成O(n2logn)O(n^2logn)

那还用这个算法干什么呢……

T(n)=O(n)+O(nlogn)+T(SizeSubtree)T(n)=O(n)+O(n*\log n)+\sum T(Size_{Subtree})

分别为:深搜,排序,和递归完成。

其中这个子树大小是非常不确定的。假如说输入的数据退化成了一个链,那么每次的子树大小就为n1n-1,想一想发现,时间复杂度还真的到了O(n2logn)O(n^2\log n)!这样是不行的!


所以我们需要引进一个新的概念,叫“树的重心”!

##树的重心

我们可以从刚才上面的式子中看到,我们需要使子树的大小尽可能小,才能减小时间复杂度;这要求我们在将无根树转化成有根树的时候,选择需要有一定的策略。幸运的是,这个最优选择点已经被人定义出来了,这便是“树的重心”。

为了利用他人解释过的东西,同时在正式开始码这道题之前有扎实的模块编码基础,我随手拉了道题来做做:POJ1655.

这道题要求我们求的就是重心,题目描述的就是定义。

思考一下,怎么求到每个节点的最大子树大小呢?注意这里的子树指以这个节点为根的树,因为树还没有定型(正要靠这个东西来定根节点呢),所以要考虑的子树还包括向父亲节点方向的子树。

我们还是做一遍DFS。随便选择一个节点(这个的选择真的无所谓,我选择的是1)做临时根节点,开始遍历。通过遍历我们可以得到在当前树下每个节点的每个子树大小,通过这个信息以及总结点数,我们可以求出每个节点最后一棵子树(也就是从向父亲方向遍历的子树)的大小:

SizeFather=n1SizeSonSize_{Father}=n-1-\sum Size_{Son}

再取所有子树的最大值就可以知道平衡值:

BalanceNode=max{SizeSon}Balance_{Node}=max\{Size_{Son}\}

这真是太~好了!只需要一遍O(n)的DFS就知道所有节点的平衡值,取其最小,就可以保证点分治问题中子树不会太大了。

可以自己使用反证法尝试证明这样子取出来的“树之重心”的子树大小不会超过n2\frac {n} {2}。假如说我们每次选取点的时候,都使用树的重心,那么套回点分治的时间复杂度,在最坏情况下(链),子树大小为n2\frac {n} {2},使用主方法将递推式转为通项公式,可以得到解法的时间复杂度:O(nlog2n)O(n\log^2 n)

POJ1655 AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#define N 20010
#define INF 2147483647
using namespace std;
int ntop,to[N<<1],bro[N<<1],head[N],fa[N],bal[N],size[N],p,n;
inline void add_edge(int u,int v){
    to[ntop]=v;
    bro[ntop]=head[u];
    head[u]=ntop++;
}
inline void apmax(int &a,int b){
    if(b>a){
        a=b;
    }
}
void dfs(int x){
    size[x]=1;
    for(int i=head[x];i;i=bro[i]){
        if(to[i]!=fa[x]){
            fa[to[i]]=x;
            dfs(to[i]);
            size[x]+=size[to[i]];
            apmax(bal[x],size[to[i]]);
        }
    }
    apmax(bal[x],n-size[x]);
    if(bal[x]<bal[p]){
        p=x;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tot,a,b;
    for(cin>>tot;tot--;){
        p=0;
        ntop=1;
        memset(head,0,sizeof(head));
        memset(fa,0,sizeof(fa));
        memset(bal,-1,sizeof(bal));
        bal[p]=INF;
        cin>>n;
        for(int i=1;i<n;i++){
            cin>>a>>b;
            add_edge(a,b);
            add_edge(b,a);
        }
        dfs(1);
        cout<<p<<" "<<bal[p]<<endl;
    }
}

15910488 sshockwave 1655 Accepted 1356K 235MS G++ 896B 2016-08-07 08:42:50

这是我第一次在POJ上一次性AC!对此我非常骄傲!但这只能说明我的实力太弱了,第一遍永远过不了。

AC之路

POJ1741不愧是男人八题之一,做这道题的时候可没有上面那道题那么幸运了,费尽了我的洪荒之力,终于AC了。

全程回顾:

Version 1

15910996 sshockwave 1741 Time Limit Exceeded G++ 2261B 2016-08-07 11:02:333

这一个源码出的主要问题在于DFS时访问节点之后没有很好的记录,导致重复访问。

Version 2

15911047 sshockwave 1741 Time Limit Exceeded G++ 2077B 2016-08-07 11:13:36

学习了一下网上的代码,cntpair函数使用了一种更低效但是写起来更方便而且保证更准确的方法,全部遍历完一遍再一个一个遍历;而之前是一个一个遍历完之后再直接把结果汇总起来计算总的可能数。原来的写法我怕有隐性的、检查不出来的问题,所以就改成了网上的写法。

Version 3

15911107 sshockwave 1741 Runtime Error G++ 2025B 2016-08-07 11:24:59

因为上一个版本超时,这一个版本便尝试优化,虽然心里挺清楚不是题目卡常……我将dfs_cent取树的重心的储存bal值最小的变量提到了全局的g,但是并没有什么用,反而还RE了。我还记得这个版本在调试的时候出的一个很大的问题:在第一层solve递归之后,第二层永远是一个子树大小为1的节点。用输出语句一句一句定位之后发现问题出在了solve上,在传入临时根的节点的时候是没有问题的,但是找到的重心就跑到别的子树上去了。于是我就发现在求重心之前g没有初始化!

Version 4

15911168 sshockwave 1741 Wrong Answer G++ 2098B 2016-08-07 11:36:47

接着WA……我已经接近崩溃边缘了。

这个版本更改了记录节点是否已访问的方式,设置father变量。这个版本一个很大的bug:忘记在dfs_depth中设置fa变量了!也许这还是前面RE、TLE、TLE的原因所在!改了这么久终于发现这个小小的问题!在信息竞赛的题目中,一个很小很小的错误,也许漫不经心,也许一不谨慎,就会造成毁灭性的的错误,直接爆零!

等一下。

源码中好像还有什么不对。

刚刚我提到,信息竞赛中细节很重要。

我为了调试方便,将输入数据保存在文件里面,貌似忘了关掉。

Version AC

15912014 sshockwave 1741 Accepted 1412K 563MS G++ 2116B 2016-08-07 15:12:18

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 10010
#define INF 2147483647
using namespace std;
int to[N<<1],bro[N<<1],len[N<<1],head[N],ntop,cnt,
    bal[N],size[N],k,depth[N],fa[N],dtop,g;
bool vis[N];
inline void add_edge(int u,int v,int val){
    to[ntop]=v;
    len[ntop]=val;
    bro[ntop]=head[u];
    head[u]=ntop++;
}
int dfs_depth(int x,int add){
//  cout<<"\t\tGetting:"<<x<<"\tdepth="<<add<<endl;
    depth[dtop++]=add;
    size[x]=1;
    for(int i=head[x];i;i=bro[i]){
        if(!vis[to[i]]&&to[i]!=fa[x]){
            fa[to[i]]=x;
            size[x]+=dfs_depth(to[i],add+len[i]);
        }
    }
    return size[x];
}
void dfs_cent(int x,int sz){
    size[x]=1;
    bal[x]=0;
    for(int i=head[x];i;i=bro[i]){
        if(!vis[to[i]]&&to[i]!=fa[x]){
            fa[to[i]]=x;
            dfs_cent(to[i],sz);
            size[x]+=size[to[i]];
            if(size[to[i]]>bal[x]){
                bal[x]=size[to[i]];
            }
        }
    }
    if(sz-size[x]>bal[x]){
        bal[x]=sz-size[x];
    }
    if(bal[x]<bal[g]){
        g=x;
    }
}
inline int cntpair(int x,int add){
    dtop=0;
    dfs_depth(x,add);
    sort(depth,depth+size[x]);
//  cout<<"\t\t\tSorting:";
//  for(int i=0;i<size[x];i++){
//      cout<<depth[i]<<" ";
//  }
//  cout<<endl;
    int sum=0;
    for(int i=0,j=size[x]-1;i<j;){
        if(depth[i]+depth[j]>k){
            j--;
        }else{
            sum+=j-i;
            i++;
        }
    }
//  cout<<"\t\t\tResult="<<sum<<endl;
    return sum;
}
void solve(int x,int sz){
//  cout<<"SOLVING "<<x<<endl;
    g=0;
    dfs_cent(x,sz);
    x=g;
//  cout<<"\tCenter:"<<x<<endl;
    vis[x]=true;
    fa[x]=x;
    cnt+=cntpair(x,0);
//  cout<<"\t\tTotal count->"<<cnt<<endl;
    for(int i=head[x];i;i=bro[i]){
        if(!vis[to[i]]){
//          cout<<"\t"<<to[i]<<endl;
            fa[to[i]]=x;
            cnt-=cntpair(to[i],len[i]);
//          cout<<"\t\tTotal count->"<<cnt<<endl;
            solve(to[i],size[to[i]]);
        }
    }
//  cout<<"Ended"<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
//  freopen("POJ1741.in","r",stdin);
    int n,a,b,v;
    bal[0]=INF;
    while(cin>>n>>k,n!=0||k!=0){
        cnt=dtop=0;
        ntop=1;
        memset(vis,0,sizeof(vis));
        memset(head,0,sizeof(head));
        memset(fa,0,sizeof(fa));
        for(int i=1;i<n;i++){
            cin>>a>>b>>v;
            add_edge(a,b,v);
            add_edge(b,a,v);
        }
        solve(1,n);
        cout<<cnt<<endl;
    }
}

此等小问题成为了我AC路上最大的绊脚石!我扑倒在桌子上,一个上午加中午的努力终于迎来了成果。

但是故事还没有结束。在这里,我还想讲讲边分治。

边分治

边分治其实和点分治十分的相似。选择一条边,将路径分为经过这条边的和不经过的,处理经过的,然后递归处理不经过的。为了保证时间复杂度能够最低,我们采取类似树的重心的策略,先DFS一遍选出边两边子树最大值最小的一条边。

但是边分治处理不好时间复杂度很容易退化成n2级别。何以见得?链状的树边分治是完全没有问题的。边分治怕的是:菊花状!

策略: 拆点!

小总结

这次做题花的调试时间远远超出考试时间,说明代码能力、纠错能力还是太弱了。当然,Dev C++这个IDE的弱小也许也是原因之一。但是这从不应该埋怨IDE,应该提高自身的算法设计能力以及思维的严谨。

在遇到枚举时间复杂度较高的情况下,可以考虑采用DP、分治、分块。我很快就会介绍分块思想。

avatar
Kerry Su