[洛谷P4178] Tree (点分治模板)

时间：2024-01-14 16:27:20

题目略了吧，就是一棵树上有多少个点对之间的距离 \(\leq k\)

\(n \leq 40000\)

算法##

首先有一个 \(O(n^2)\) 的做法，枚举每一个点为起点，\(dfs\) 一遍可知其它点到这个点的距离，统计一下即可。

但是这样太慢了。于是考虑“分治”这种神奇的做法。

第一步，选一个点做根节点，这个点便是树的重心(代码中找重心 \(getroot\) )，它满足每棵子树节点数不超过 \(n/2\) ，即可保证子问题规模减半。

第二步，寻找所有经过根节点的路径，这些路径可以写成 \(u \leadsto rt + v \leadsto rt\)

但是这样有一个问题，\(u\) 和 \(v\) 的 \(lca\) 可能不是 \(rt\) ，即 \(u \leadsto v\) 不经过 \(rt\)

于是我们用容斥原理，枚举 \(rt\) 的每一个儿子把这种情况减去(代码 \(work\) 中的 $ ans-=cal(v,p \to len)$)

顺便提一句如何计算有多少小于 \(k\) 的路径，两个指针扫来扫去就行了(代码中的 \(cal\) )

复杂度 \(O(n)\)

第三步，对于 \(rt\) 的每一棵子树进行递归（第一步）。

分析##

个人认为算法的重点有两个：

  1. \(cal\) 复杂度可为 \(O(n)\)

    2.重心可使每棵子树规模减半

    这样就使得整个算法复杂度为 \(O(nlogn)\)

代码##

终于会点分治了，很开心啊~

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

const int N = 40005;

struct node{

    node *next;

    int v,len;

}pool[N*2],*h[N];

int cnt;

void addedge(int u,int v,int len){

    node *p=&pool[++cnt],*q=&pool[++cnt];

    p->v=v;p->next=h[u];h[u]=p;p->len=len;

    q->v=u;q->next=h[v];h[v]=q;q->len=len;

}

int sum,rt,n,k;

int size[N],mx[N],vis[N];

void getroot(int u,int f){

    int v;

    size[u]=1; mx[u]=0;

    for(node *p=h[u];p;p=p->next){

        if(vis[v=p->v] || v==f) continue;

        getroot(v,u);

        size[u]+=size[v]; mx[u]=max(mx[u],size[v]);

    }

    mx[u]=max(mx[u],sum-size[u]);

    if(mx[u]<mx[rt]) rt=u;

}

int dep[N],dd;

void getdeep(int u,int f,int c){

    int v;

    dep[++dd]=c;

    size[u]=1;

    for(node *p=h[u];p;p=p->next){

        if(vis[v=p->v] || v==f) continue;

        getdeep(v,u,c+p->len);

        size[u]+=size[v];

    }

}

int cal(int u,int c){

    int t=0;

    dd=0;

    getdeep(u,0,c);

    sort(dep+1,dep+1+dd);

    for(int l=1,r=dd;l<r;l++){

        while(l<r && dep[l]+dep[r]>k) r--;

        t+=r-l;

    }

    return t;

}

int ans;

void work(int u){

    int v;

    vis[u]=1;

    ans+=cal(u,0);

    for(node *p=h[u];p;p=p->next){

        if(vis[v=p->v]) continue;

        ans-=cal(v,p->len);

        rt=0; sum=size[v]; getroot(v,u);

        work(rt);

    }

}

int main()

{

    int u,v,l;

    scanf("%d",&n);

    for(int i=1;i<n;i++){

        scanf("%d%d%d",&u,&v,&l);

        addedge(u,v,l);

    }

    scanf("%d",&k);

    mx[0]=400005;

    rt=0; sum=n; getroot(1,0);

    work(rt);

    printf("%d\n",ans);

    return 0;

}

相关文章