[POJ1741 Tree]基于点划分的树的分治算法、男人8题

【题目大意】

给出一棵树，让你求树中距离<=K的点对个数。

【算法分析】

围观了一下漆子超大神的论文。。。表示那实在太简略了。。。我只能从中得到一些启发。

首先是按他说的那样，对树进行基于点的划分。

划分的方法是：每次对当前块选一个根，使得去掉这个点以后，划分出新的各个块中点数最多的最少。

这个利用DFS搜一下，维护一个表示以该节点为根的子树的点数多少的数组size[i]。然后当前这个点当分割点，分成各个块的大小就可以很容易算出来。

划分好以后，就从划分树的底层向顶层扫描（其实这个顺序只要是拓扑序就可以了）。

扫描上去的过程中，将划分树当前区间的点都放进一个队列里面，并将它们按到“划分点”的距离排个序。

然后用j从前面开始扫描，并维护另一个指针k，指向一个点满足k=max(k : dis[Q[k]]+dis[Q[j]]<=K)。

接着再减去那些与当前点在下一层里属于同一个划分区间的点的数量，就是经过该根并满足<=K的路径的数量。把它们全加起来就是ans。

【其他】

写了个朴素对拍调试才A。。。之前因为维护k指针的时候k–写在那个if前面了，所以搞错了。。。

终于成为了1/2个男人

【CODE】

#include #include #include #include #include #include using namespace std;
const int E=333333;
const int N=122222;
const int INF=1000000000;
struct edge{int x,y,w;edge *next;}g[E],*ls[N];
struct linetreetype{int l,r,dep,root;}tr[N*16];
int n,K,e,Qt,NowDep,ans;
int color[16][N],list[16][N],tot[16],dis[N],size[N];
int Q[N],use[N],done[N];

struct LineTreeFunction{
       int times,nowroot,nownum,trtot;

       void makelabel(int p,int *co,int fa){
            size[p]=times++;
            for (edge *t=ls[p];t;t=t->next)
              if (co[t->y]==co[p] && t->y!=fa){
                dis[t->y]=dis[p]+t->w;
                makelabel(t->y,co,p);
              }
            size[p]=times-size[p];
       }

       void choose_root(int p,int *co,int fa,int total){
           int now=0;
           if (fa) now=max(now,total-size[p]);
           for (edge *t=ls[p];t;t=t->next)
             if (co[t->y]==co[p] && t->y!=fa)
               now=max(now,size[t->y]);
           if (now           for (edge *t=ls[p];t;t=t->next)
             if (co[t->y]==co[p] && t->y!=fa)
               choose_root(t->y,co,p,total);
       }

       void buildnewlp(int p,int fa,int *co,int dep){
           list[dep][++tot[dep]]=p;
           for (edge *t=ls[p];t;t=t->next)
             if (co[t->y]==co[p] && t->y!=fa)
               buildnewlp(t->y,p,co,dep);
       }

       void build(int p,int l,int r,int dep){
            tr[p].l=l; tr[p].r=r; tr[p].dep=dep;
            int &st=list[dep][l];
            for (int i=l;i<=r;i++) color[dep][list[dep][i]]=p;
            if (l==r) return;
            dis[st]=0; times=0; nownum=INF;
            makelabel(st,color[dep],0);
            choose_root(st,color[dep],0,r-l+1);
            tr[p].root=nowroot;

            for (edge *t=ls[tr[p].root];t;t=t->next)
              if (color[dep][t->y]==p){
                int pt=tot[dep+1]+1,nt;
                buildnewlp(t->y,tr[p].root,color[dep],dep+1);
                nt=tot[dep+1];
                trtot++;
                build(trtot,pt,nt,dep+1);
              }
       }
}LineTree;

void addedge(int x,int y,int w){
     g[++e].x=x; g[e].y=y; g[e].w=w; g[e].next=ls[x]; ls[x]=&g[e];
}

void init(){
     e=0;
     for (int i=1;i<=n;i++) ls[i]=NULL;
     memset(color,0,sizeof(color));
     memset(list,0,sizeof(list));
     memset(tot,0,sizeof(tot));
     for (int i=1;i         int x,y,w;
         scanf("%d%d%d",&x,&y,&w);
         addedge(x,y,w);
         addedge(y,x,w);
     }
     tot[1]=n;
     for (int i=1;i<=n;i++) list[1][i]=i;
}

bool cmp(int x,int y){
    return (dis[x])<(dis[y]);
}

void work(){
    ans=0;
    memset(use,0,sizeof(use));
    memset(done,0,sizeof(done));
    for (int i=LineTree.trtot;i>=1;i–){
        if (tr[i].l==tr[i].r) continue;
        dis[tr[i].root]=0;
        LineTree.times=0;
        LineTree.makelabel(tr[i].root,color[tr[i].dep],0);
        NowDep=tr[i].dep+1;
        Qt=0;
        int j,k=0;
        for (j=tr[i].l;j<=tr[i].r;j++)
          Q[++Qt]=list[tr[i].dep][j];
        sort(Q+1,Q+Qt+1,cmp);
        int *co=color[tr[i].dep+1];
        for (j=1;j<=Qt;j++){
          if (co[Q[j]] && use[co[Q[j]]]!=i){
              use[co[Q[j]]]=i;
              done[co[Q[j]]]=0;
          }
          while (k+1            k++;
            if (co[Q[k]])
              done[co[Q[k]]]++;
          }
          while (k>0 && dis[Q[j]]+dis[Q[k]]>K){
            if (co[Q[k]])
              done[co[Q[k]]]–;
            k–;
          }
          ans+=k-done[co[Q[j]]];
        }
    }
}

int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    for (;;){
        scanf("%d%d",&n,&K);
        if (!n && !K) break;
        init();
        LineTree.trtot=1;
        LineTree.build(1,1,n,1);
        work();
        cout << ans << endl;
    }
}