0阶段-第七日-树上启发式式合并

必须摸了...不摸,就无法生存。
第七日,树上启发式式合并。
0阶段-第七日-树上启发式式合并

1~3、树上启发式合并
4、树上倍增+启发式合并
虽然式四道紫题,但是会写一题之后其余三题相对很容易的。整理如下:
一、树上启发式合并
0、前置:

  • 重孩子:父节点的所有孩子节点中子树节点数最多的那个节点
  • 轻孩子:除了重节点外其它兄弟节点
  • 启发式:一个基于直观或经验构造的思维方法。比如并查集的按秩合并,装果子的贪心策略,都是可以凭借直觉或经验感知出来的方法。

1、当遇上一些树形dp难以转移的状态,可能面临空间复杂度过高无法实现,但暴力却又时间复杂度过高。
2、模板题树上数颜色,数据纯随机,非常弱
3、状态难以转移(空间不够)。但是暴力会超时。
4、由启发式思想得到方法:求一颗子树的颜色种数的时候,只继承根节点的重儿子的状态,而其余轻儿子选择清空,然后另写一函数暴力遍历一边。 我们可以找到方法转移状态且降低了时间复杂度。看似暴力遍历实则把时间复杂度削减至O(nlogn)
5、主干代码:

void dfs2(int u,int fa,bool keep){//keep为0表示清楚,keep为1代表保留
    for(int i=g.h[u];i;i=g.e[i].pre){
        int v=g.e[i].to;
        if(v==fa||v==heavy[u]) continue;
        dfs2(v,u,0);
    }//遍历轻儿子
    if(heavy[u]) dfs2(heavy[u],u,1);//遍历重儿子,出来后状态仍然保留
    flag=heavy[u];//记录重儿子,以便二次扫描时continue

    compute(u,fa,1);//二次扫描除了重儿子外的整棵子树,第三个参数是1用于计数
    ans[u]=sum;//得出答案赋值
    flag=0;//清除标记,下次compute第三次次扫描整棵子树(如果keep==0)
    if(!keep){//0的化
        compute(u,fa,-1);//第三次扫描,-1用于清楚计数,切记不可使用memset
        sum=maxc=0;
    }
}

6、compute代码

void compute(int u,int fa,int val){
    cnt[num[u]]+=val;
    if(cnt[num[u]]>maxc){
        maxc=cnt[num[u]];
        sum=num[u];//变大就更新
    }
    else if(cnt[num[u]]==maxc) sum+=num[u];//相等就加上
    
    for(int i=g.h[u];i;i=g.e[i].pre){
        int v=g.e[i].to;
        if(v==fa||v==flag) continue;
        compute(v,u);
    }
}

**二、时间复杂度的说明 **
0、前置

  • 从孩子节点到根节点的简单路径中最多有logn条轻边,没有证明,或许树链分剖会说明。
  • 轻边:轻孩子和父亲连接的那条边

1、不计入compute的时间复杂度,启发式合并整体上就是树的遍历,时间复杂度为O(n)。
2、考虑每个节点对于compute的时间复杂度的贡献
3、从前置知,从节点到根最多大约有logn条轻边也就是最多有n个轻节点,每个轻节点最多会做两次compute,一次是它做为轻孩子被二次扫描的时候,另一次是作为轻孩子因为keep为0被清空的时候。也就是说一个节点最多会被扫描2logn次,一共n个节点。所以时间复杂度为O(nlogn)。

上一篇:数据的类型


下一篇:javaScript