点分治学习笔记

· · 个人记录

前言

淀粉是高分子碳水化合物，是由葡萄糖分子聚合而成的。其基本构成单位为α-D-吡喃葡萄糖，分子式为(C6H10O5 )n。 -- 百度百科

淀粉质食物，主要指富含碳水化合物的食物以及根茎类蔬菜。 -- 百度知道

模板题

点分治总体思想：

设u的子节点为v，对于v的子树，统计v子树的答案，最后通过v子树的答案计算u子树的答案。

样例分析

我们假设以u为根的子树的解的个数是f_u。

对于1号节点作为根的子树，可以向下分治为两棵以2为根和以3为根的子树，再向下分治…… 最后到了叶节点，直接算出f_u
我们向上回溯，由f_{10}和f_{11}得到了f_7，由f_8和f_9得到了f_4，然后由f_5，f_6和f_7得到了f_3……

最后得到了f_1

这显然是树形 DP 的思想，每次求f_u的话就遍历u的子树，然后讲他们到u的距离排序，双游标去看有多少个是k的

但是我们看一下这题（模板题）

有边权的树，问有多少条长不超过k的路径

DP：设f_u为经过点u且在u子树中的答案，我们可以先给u子树的节点按照到u的距离排序，然后双游标计算出u子树中到u距离<k的点对数。设其为k_u。最后要去掉在v子树中且过点v的路径数量，因为这些东西在v的答案中计算过。（相当于一个容斥）

f_u=k_u-\sum\limits_{v\in son_u}f_v ans=\sum f_u

这样的话，每次转移的时间是O(size_u) ，总体时间是O(n^2)

有没有更简便的方法呢？显然是有的。我们需要让size_u平均尽可能地小，那么既然和size_u关系比较大，我们想到使得size_u平均最小地情况应该是取的重心为根时，size_u最大是整个子树的一半。

所以我们换根为重心。

我们取出了重心，有了一些新的子树(黄色圈出来的)

这样，复杂度控制在O(n\sum \frac{size_u}{2})，就是O(nlogn)的时间

现在总体步骤已经确定了，对于子树u，先计算出k_u，然后求出每个子树v的重心，分治那个重心r作为子树的根，算出f_v，然后再回溯算出f_u

算法步骤

对于计算出u的子树的分治函数：

  1. 枚举+排序+双游标算出k_u
  2. 枚举儿子节点v
    1. 算出v子树的重心r
    2. 换根为r，重新算到根的距离
    3. 分治计算r
    4. 用f_v更新f_u

其实其他点分治也差不多是这样的，不过重新计算和求f_u的方法会略有不同。

#include<bits/stdc++.h>
using namespace std;
const int N=50009;
int n,k,ans;
struct tree{
    struct edge{int to,nxt,w;}e[N*2]; int hd[N],tot;
    void add(int u,int v,int w){e[++tot]=(edge){v,hd[u],w};hd[u]=tot;}
    int mx[N],sz[N],d[N]; bool vst[N];

    int find_root(int u,int fa,int cnt,int root){
        mx[u]=0,sz[u]=1; 
        for(int i=hd[u],v;i;i=e[i].nxt)
            if((v=e[i].to)!=fa&&!vst[v]){
                root=find_root(v,u,cnt,root);
                mx[u]=max(mx[u],sz[v]), sz[u]+=sz[v];
            }
        mx[u]=max(mx[u],cnt-sz[u]); if(mx[u]<=(cnt+1)/2.) root=u; 
        return root;
    }

    int p[N],cnt;
    void update(int u,int fa){
        p[++cnt]=d[u]; sz[u]=1;
        for(int i=hd[u],v;i;i=e[i].nxt)
            if((v=e[i].to)!=fa&&!vst[v])
                d[v]=d[u]+e[i].w,update(v,u),sz[u]+=sz[v];
    }

    int cal(int u,int base,int ret=0){
        d[u]=base,cnt=0,update(u,-1);
        sort(p+1,p+cnt+1);
        int l=1,r=cnt; while(l<r) p[l]+p[r]<=k? ret+=(r-(l++)):r--;
        return ret;
    }
    void dfz(int u){
        vst[u]=1; ans+=cal(u,0);
        for(int i=hd[u],v;i;i=e[i].nxt)
            if(!vst[(v=e[i].to)])
                ans-=cal(v,e[i].w),dfz(find_root(v,u,sz[v],0));
    }
}tr;
int main(){
    scanf("%d",&n);
    for(int i=1,u,v,w;i<n;i++)
        scanf("%d%d%d",&u,&v,&w),tr.add(u,v,w),tr.add(v,u,w);
    scanf("%d",&k);
    tr.dfz(tr.find_root(1,-1,n,0)); printf("%d",ans);
    return 0;
}