点分治哦亲~~_牛客博客

说一下

点分治、感觉还看的懂。
经典问题：找一个树上距离为k的有多少对点。
怎么找呢？分治思想：递归
也就是找一个合适的根然后把问题分为跨过这个根的两个点和不过这个根的距离也就是在一个子树上的两个点和不在同一个子树上的两个点。处理的时候只处理不过这个根的距离（在同一个子树上的）有没有为k的。因为不过这个根的情况在以后会处理到的。然后删掉这个根对他的子树进行上述操作。
找根的时候如果按题上给的根做可能会超时;最坏的时候，对于1->2->3->4->5这种情况时间复杂度是n^2，但是理想的是n*logn由于用哪个节点当根对结果没有影响，所以如果自己重新找个根可能让时间复杂度低一点对于上述情况就是找3这个节点当根复杂度最低，也就是这个链的中点。但是对于树就没有中点这个概念了。
于是有个东西叫重心：就是找一个节点，让这个节点的最大子树最小这个点就叫重心。每次找他的重心当根就可以了。
找重心怎么找？也就是一遍dfs处理出以这个节点为根的子树的大小。再用个数组记录这个节点所有子树中最大的子树大小，然后找个最小的。
分治递归的时候找距离怎么找？也是dfs 找目前节点到根节点的距离记录在temp数组中。然后进行自己要做的处理。

代码

第一道水题，板子题：
洛谷板子题

#include <queue>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
struct Node
{
   
    int id,val;
};
const int maxn = 1e5+5;
vector<Node> vv[maxn];//存图
int root;//重心 就是 树中以该节点为根的最大子树最小
int num[maxn];//标记以他为根的树的点的个数
int vis[maxn];//标记是否删除
int son[maxn];//代表以它为根的最大的子树
int sum;//因为 以当前点为根节点时 他的父节点也是他的一个子节点 当前根dfs时父节点的子树大小=总的节点个数减去他的子节点的子树节点个数 sum用来存总的个数 
void dfs(int x,int fa)//这个dfs部分感觉跟树链刨分的 那个dfs差不多 
{
   
	son[x]=0;//初始化 记得！！！ 
    num[x]=1;//节点数量初始为1 
    for (int i=0;i<vv[x].size();i++)
    {
   
        Node t=vv[x][i];
        int v=t.id;
        if(v==fa||vis[v]==1)
        {
   
            continue;
        }
        dfs(v,x);
        num[x]+=num[v];
        if(num[v]>son[x])//son[x]存的是x的子树中最大的子树的节点个数
            son[x]=num[v];
    }
    if(sum-num[x]>son[x])//他dfs时的父节点作为他的子节点的子树大小
    {
   
        son[x]=sum-num[x];
    }
    if(root==-1||son[root]>son[x])//root应为最大字数最小的那个节点
        root=x;
}
int q[maxn];//询问
int kk;//kk个询问
bool ans[maxn];//询问的答案
int cnt;//用来计数 得到距离时 计数
int dis[maxn];//存根节点到当前节点的距离
bool judge[10000007];//用来判断 该距离是否存在 

int temp[maxn];//临时用来存距离
void getdis(int x,int fa)//这个也是递归
{
   
    temp[cnt++]=dis[x];//把dis里的存下来
    for(int i=0;i<vv[x].size();i++)
    {
   
        Node t=vv[x][i];
        int v=t.id;
        if(vis[v]||v==fa)
            continue;
        dis[v]=dis[x]+t.val;//更新dis值
        getdis(v,x);//继续找根节点到v的距离
    }
}
void solve(int x)
{
   
    queue<int> qq;//这个队列好像他妈的没用啊 但是 讲解视频说这个是队列优化 有用有用 看下面！！！
    for (int i=0;i<vv[x].size();i++)
    {
   
        Node t=vv[x][i];
        int v=t.id;
        if(vis[v])
            continue;
        cnt=0;//记得初始化计数的这个值 
        dis[v]=t.val;
        getdis(v,x);//得到temp数组 即得到v子树中每个节点到v的距离
        //printf("%d\n",cnt);
        for(int j=0;j<cnt;j++)//遍历得到的temp数组
        {
   
            for (int k=0;k<kk;k++)//遍历询问
            {
   
                if(q[k]>=temp[j])//条件 不然下面减成负的了
                {
   
                    //printf("%d\n",ans[k]);
                    ans[k]|=judge[q[k]-temp[j]];//这个子树上的距离到另一个子树上的距离和为q[k]的 看是否存在 
                    //为什么不判断同一个子树上 两点距离有q[k]的 ？？ 因为 以后会判断的 这里只判断过u点的边 的距离是否有 q[k]
                }
            }
        }
        for (int j=0;j<cnt;j++)//队列好像就这下面用了一下 可是有什么用呢 看下面 有用有用！！！
        {
   
            qq.push(temp[j]);
            judge[temp[j]]=true;//现在把这些距离标记为存在 因为遍历下一个子树的时候可能用到
        }
    }
    while(!qq.empty())//奥对 有用 有用 只是用来存一下各个子树里temp数组的值 以便于 把他们删除 变为不存在
    {
   
        judge[qq.front()]=false;//遍历完了 把这些距离变为不存在
        qq.pop();
    }
}


void fenzhi(int x)//分治 基本就变一变solve？??我猜的
{
   
    vis[x]=1;//删除x节点
    dis[x]=0;//x到x是0
    judge[0]=true;//距离为0肯定存在
    solve(x);//遍历x的子树 找距离
    for (int i=0;i<vv[x].size();i++)//把x删了 遍历他的子树 在他的每个子树中找个重心 继续这样递归
    {
   
        Node t=vv[x][i];
        int v=t.id;
        if(vis[v]==1)
            continue;
        root=-1;//记得这两个初始化
        sum=num[v];//记得 
        dfs(v,x);//找重心 记得找两次 因为 num得是以root为根的子树大小
        dfs(root,-1);
        fenzhi(root);
    }
}

int main()
{
   
    int n;
    scanf("%d%d",&n,&kk);
    for (int i=0;i<n-1;i++)
    {
   
        int x,y,val;
        scanf("%d%d%d",&x,&y,&val);
        Node t;
        t.id=y;
        t.val=val;
        vv[x].push_back(t);
        t.id=x;
        vv[y].push_back(t);
    }
    for (int i=0;i<kk;i++)
    {
   
        scanf("%d",&q[i]);
    }
    root=-1;
    sum=n;
    dfs(1,-1);//得到根节点
    dfs(root,-1);// 再跑一遍是为了得到以root为根的子树的大小
    //printf("%d\n",root);
    fenzhi(root);//分治找距离
    for (int i=0;i<kk;i++)
    {
   
        if(ans[i])
            printf("AYE\n");
        else
            printf("NAY\n");
    }
}

第二道：
洛谷第二个板子题

#include <queue>
#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int maxn = 40006;
struct Node
{
   
    int id,val;
};
int m;
vector<Node> vv[maxn];
int summ[200005];
int lowbit(int x)
{
   
    return x&-x;
}
void add(int x,int num)
{
   
    while(x<=m)
    {
   
        summ[x]+=num;
        x+=lowbit(x);
    }
}
int query(int x)
{
   
    int ans=summ[0];
    while(x>0)
    {
   
        ans+=summ[x];
        x-=lowbit(x);
    }
    return ans;
}

int num[maxn];
int son[maxn];
int sum,root;
int vis[maxn];

void dfs(int x,int fa)
{
   
    num[x]=1;
    for (int i=0;i<vv[x].size();i++)
    {
   
        Node t=vv[x][i];
        int v=t.id;
        if(v==fa||vis[v]==1)
            continue;
        num[x]+=num[v];
        if(num[v]>son[x])
            son[x]=num[v];
    }
    if(sum-num[x]>son[x])
        son[x]=sum=num[x];
    if(root==-1||son[root]>son[x])
        root=x;
}
int dis[maxn];
int temp[maxn];
int cnt=0;
int ans=0;
void getdis(int x,int fa)
{
   
    temp[cnt++]=dis[x];
    for (int i=0;i<vv[x].size();i++)
    {
   
        Node t=vv[x][i];
        int v=t.id;
        if(vis[v]==1||v==fa)
            continue;
        dis[v]=dis[x]+t.val;
        getdis(v,x);
    }
}
void solve(int x)
{
   
    //printf("%d\n",x);
    //vis[x]=1;
    queue<int> qq;
    for (int i=0;i<vv[x].size();i++)
    {
   
        Node t=vv[x][i];
        int v=t.id;
        if(vis[v])
            continue;
        cnt=0;
        dis[v]=dis[x]+t.val;
        getdis(v,x);
        for (int j=0;j<cnt;j++)
        {
   
            int p=m-temp[j];
            if(p>=0&&p<=m)
                ans+=query(p);
            //printf("%d %d %d\n",ans,p,temp[j]);
        }
        for (int j=0;j<cnt;j++)
        {
   
            if(temp[j]>=0&&temp[j]<=m)
            {
   
                add(temp[j],1);
                qq.push(temp[j]);
            }

        }
    }
    while(!qq.empty())
    {
   
        add(qq.front(),-1);
        qq.pop();
    }
}


void fenzhi(int x)
{
   
    //printf("%d\n",x);
    vis[x]=1;
    dis[x]=0;
    summ[0]=1;
    solve(x);
    for (int i=0;i<vv[x].size();i++)
    {
   
        Node t=vv[x][i];
        int v=t.id;
        if(vis[v])
            continue;
        sum=num[v];
        root=-1;
        dfs(v,x);
        dfs(root,-1);
        fenzhi(root);
    }
}

int main()
{
   
    int n;
    scanf("%d",&n);
    for (int i=1;i<n;i++)
    {
   
        int x,y,val;
        scanf("%d%d%d",&x,&y,&val);
        Node t;
        t.id=y;
        t.val=val;
        vv[x].push_back(t);
        t.id=x;
        vv[y].push_back(t);
    }
    scanf("%d",&m);
    root=-1;
    sum=n;
    dfs(1,-1);
    dfs(root,-1);
    //printf("%d\n",root);
    fenzhi(root);

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

然后还有几道可以去练：
洛谷p2634
洛谷p2664
洛谷p4149
CF161D

在b站上学的，感谢

点分治哦 亲~~

说一下

代码

点分治哦亲~~