（模板）luoguP3806（树上点分治模板题）

点分治的写法1：

题目链接：https://www.luogu.org/problem/P3806

题意：给出一颗带边权的树，结点数n<=1e4，每条边有权值<=1e4，有m组询问（m<=100），每组询问为一个k，表示是否存在一条路经长度为k，存在输出AYE，不存在输出NAY。

思路：点分治模板题，第一次学点分治。这位聚聚的讲解特别好，安利一波：https://blog.csdn.net/a_forever_dream/article/details/81778649。

　　　写法1：先计算所有组合情况，然后删除全部在子树中的路径，再递归求解。这种写法一般在统计答案时要排序，根据单调型或二分查找。常数比写法二要大。

AC代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int inf=0x3f3f3f3f;

const int maxn=;

struct node1{

    int v,w,nex;

}edge[maxn<<];

struct node2{

    int x,y;

}arr[maxn];

int n,m,cnt,size;

int head[maxn],root,Min,sz[maxn],mson[maxn],vis[maxn];

int t,tt,dis[maxn],ask[],ans[];

void adde(int u,int v,int w){

    edge[++cnt].v=v;

    edge[cnt].w=w;

    edge[cnt].nex=head[u];

    head[u]=cnt;

}

void getroot(int u,int fa){

    sz[u]=,mson[u]=;    //mson记录最大子树的大小

    for(int i=head[u];i;i=edge[i].nex){

        int v=edge[i].v;

        if(vis[v]||v==fa) continue; //vis记录是否分治过

        getroot(v,u);

        sz[u]+=sz[v];

        if(sz[v]>mson[u]) mson[u]=sz[v];

    }

    if(size-sz[u]>mson[u]) mson[u]=size-sz[u];

    if(Min>mson[u]) Min=mson[u],root=u;

}

void getdis(int u,int fa,int len){  //len表示u到目标点的距离

    dis[++t]=len;

    for(int i=head[u];i;i=edge[i].nex){

        int v=edge[i].v;

        if(v==fa||vis[v]) continue;

        getdis(v,u,len+edge[i].w);

    }

}

void solve(int x,int y,int f){  //x是geidis的起点，y是x到目标点的距离，f表示合法还是不合法

    t=;

    getdis(x,,y);     //算出树中点到目标点的距离

    tt=;

    sort(dis+,dis+t+);

    dis[]=-;

    for(int i=;i<=t;++i) //把距离相等的整合在一起，方便处理

        if(dis[i]!=dis[i-]) arr[++tt].x=dis[i],arr[tt].y=;

        else ++arr[tt].y;

    for(int i=;i<=m;++i){

        if(ask[i]%==)   //单独处理到根的距离为k/2的点，它们不需二分

            for(int j=;j<=tt;++j)

                if(arr[j].x==ask[i]/)

                    ans[i]+=(arr[j].y-)*arr[j].y/*f;

        for(int j=;j<=tt&&arr[j].x<ask[i]/;++j){ //仅枚举小于k/2的

            int l=j+,r=tt,mid;

            while(l<=r){

                mid=(l+r)>>;

                if(arr[j].x+arr[mid].x==ask[i]){

                    ans[i]+=arr[j].y*arr[mid].y*f;

                    break;

                }

                if(arr[j].x+arr[mid].x>ask[i]) r=mid-;

                else l=mid+;

            }

        }

    }

}

void fenzhi(int u,int ssize){    //ssize是当前这颗子树的大小

    vis[u]=;

    solve(u,,);          //计算这颗树以u为重心的所有组合

    for(int i=head[u];i;i=edge[i].nex){

        int v=edge[i].v;

        if(vis[v]) continue;

        solve(v,edge[i].w,-); //减去不合法组合

        Min=inf,root=;

        size=sz[v]<sz[u]?sz[v]:(ssize-sz[u]);

        getroot(v,);

        fenzhi(root,size);

    }

}

int main(){

    scanf("%d%d",&n,&m);

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

        int u,v,w;

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

        adde(u,v,w);

        adde(v,u,w);

    }

    for(int i=;i<=m;++i)

        scanf("%d",&ask[i]);

    root=,Min=inf,size=n;

    getroot(,);

    fenzhi(root,n);

    for(int i=;i<=m;++i)

        if(ans[i]>) printf("AYE\n");

        else printf("NAY\n");

    return ;

}

点分治写法2：

题目链接:https://www.luogu.org/problem/P4149

题意：给定一颗树，求路径长为k的边数最小的路径，求最小边数。

思路：点分治裸体。写法2按子树依次递归进入，进入后先统计答案，再统计相关值，一般用桶来统计。统计答案用到了前面子树的信息。写法2的常数小于写法1。

AC代码：

#include<cstdio>

#include<algorithm>

#include<cctype>

using namespace std;

const int maxn=;

const int maxk=;

const int inf=0x3f3f3f3f;

inline int read(){

    int x=,f=;char c=;

    while(!isdigit(c)) {f|=c=='-';c=getchar();}

    while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();

    return f?-x:x;

}

struct node{

    int v,w,nex;

}edge[maxn<<];

int n,ans=inf,cnt,k,head[maxn],root,size,Min,sz[maxn],mson[maxn];

int vis[maxn],mine[maxk],dis1[maxn],dis2[maxn],t,tt;

void adde(int u,int v,int w){

    edge[++cnt].v=v;

    edge[cnt].w=w;

    edge[cnt].nex=head[u];

    head[u]=cnt;

}

void getroot(int u,int fa){

    sz[u]=,mson[u]=;

    for(int i=head[u];i;i=edge[i].nex){

        int v=edge[i].v;

        if(vis[v]||v==fa) continue;

        getroot(v,u);

        sz[u]+=sz[v];

        if(sz[v]>mson[u]) mson[u]=sz[v];

    }

    if(size-sz[u]>mson[u]) mson[u]=size-sz[u];

    if(mson[u]<Min) Min=mson[u],root=u;

}

void getdis(int u,int fa,int d1,int d2){

    if(d1>k) return;

    dis1[++t]=d1,dis2[t]=d2;

    for(int i=head[u];i;i=edge[i].nex){

        int v=edge[i].v;

        if(vis[v]||v==fa) continue;

        getdis(v,u,d1+edge[i].w,d2+);

    }

}

void solve(int u){

    mine[]=,t=;  //考虑一个端点是u的情况

    for(int i=head[u];i;i=edge[i].nex){

        int v=edge[i].v;

        if(vis[v]) continue;

        tt=t;

        getdis(v,u,edge[i].w,);

        for(int j=tt+;j<=t;++j)  //更新答案

            ans=min(ans,mine[k-dis1[j]]+dis2[j]);

        for(int j=tt+;j<=t;++j)  //更新桶

            mine[dis1[j]]=min(mine[dis1[j]],dis2[j]);

    }

    for(int i=;i<=t;++i)

        mine[dis1[i]]=inf;

}

void fenzhi(int u,int ssize){

    vis[u]=;

    solve(u);

    for(int i=head[u];i;i=edge[i].nex){

        int v=edge[i].v;

        if(vis[v]) continue;

        Min=inf,root=;

        size=sz[v]<sz[u]?sz[v]:(ssize-sz[u]);

        getroot(v,);

        fenzhi(root,size);

    }

}

int main(){

    n=read(),k=read();

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

        int u=read()+,v=read()+,w=read();

        adde(u,v,w);

        adde(v,u,w);

    }

    Min=inf,root=,size=n;

    getroot(,);

    for(int i=;i<=k;++i)

        mine[i]=inf;

    fenzhi(root,n);

    printf("%d\n",ans<n?ans:-);

    return ;

}