淀粉质学习笔记

· · 个人记录

什么是淀粉质点分治:

看到分治这两个字是不是特别熟悉？

分治算法有很多，点分治就是其中之一。

数列上的分治，就是把数列分成[1,mid][mid+1,n]来处理，不能分为像[1,1][2,n]这样，这样的话分治法就会退化为暴露枚举。

树上的点分治也是基于将树二等分的思想，主要用于处理树上路径问题。

点分治的思想(重心分解) 1.树的重心定义为删去该重心root，那么剩下的每颗子树v的size[v]都不超过size[root]/2。 2.处理包含root的情况，如求树上路径为k的点对是否存在，需要考虑root在这条路径上的情况。 3.其余情况递归到子树处理

点分治的时间复杂度分析:

首先每次寻找重心递归处理，使得每次处理规模减半，所以时间复杂度为O(nlogn)

点分治的实现：

例题1：P4178 Tree

题意：求距离小于等于k的点对数量

分析：

先寻找重心，执行一次深度优先遍历统计子树的节点数，找不超过size[n]/2最大的一个

然后统计每个子树节点对于重心的距离，存入dep[]中。

执行一次排序，从小到大，方便于使用双指针扫描法快速统计答案

最终答案加等于包含root节点的答案

然后减去重复统计的就是root真正贡献的答案

Code 
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10005;
int cnt,n,k,ans,head[maxn];
int root,S,size[maxn],f[maxn],d[maxn],dep[maxn];
bool vis[maxn];
struct edge
{
    int to,next,w;
}edge[maxn*2];

void add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void getroot(int u,int fa)//获取重心
{
    size[u]=1;
    f[u]=0;//删除u后，最大子树的大小 
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v!=fa&&!vis[v])
        {
            getroot(v,u);
            size[u]+=size[v];
            f[u]=max(f[u],size[v]);
        }
    }    
    f[u]=max(f[u],S-size[u]);//S为当前子树总结点数 
    if(f[u]<f[root])
        root=u;
}

void getdep(int u,int fa)//获取距离
{
    dep[++dep[0]]=d[u];//保存距离数组 
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v!=fa&&!vis[v])
        {
            d[v]=d[u]+edge[i].w;
            getdep(v,u);
        }
    }
}

int getsum(int u,int dis) //获取u的子树中满足个数
{
    d[u]=dis;
    dep[0]=0;
    getdep(u,0);
    sort(dep+1,dep+1+dep[0]);
    int L=1,R=dep[0],sum=0;
    while(L<R)
        if(dep[L]+dep[R]<=k)
            sum+=R-L,L++;
        else
            R--;
    return sum;
}

void solve(int u) //获取答案
{
    vis[u]=true;
    ans+=getsum(u,0);
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(!vis[v])
        {
            ans-=getsum(v,edge[i].w);//减去重复
            root=0;
            S=size[v];
            getroot(v,u);
            solve(root);
        }
    }
}

int main()
{
    f[0]=0x7fffffff;//初始化树根 
    while(scanf("%d%d",&n,&k),n+k)
    {
        memset(vis,0,sizeof(vis));
        memset(head,0,sizeof(head));
        cnt=0;ans=0;
        for(int i=1;i<=n-1;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
            add(y,x,z);
        }
        root=0;
        S=n;
        getroot(1,0);
        solve(root);
        printf("%d\n",ans);
    }
    return 0;
}

例题2：

鸽子