首页 > 其他分享 >树上启发式合并

树上启发式合并

时间:2022-11-16 21:24:06浏览次数:71  
标签:cnt int sum dsu 合并 son 启发式 树上 col

树上启发式合并,DSU On Tree,静态链分治,用于求解支持离线的树上子树查询问题。

暴力做法,每次做完一棵树就要把它清空,避免对它兄弟造成影响,但是做到它的祖先时又会重新对它做一遍,发现最后一棵树是不需要清空的,于是考虑将节点数最多的留到最后。

首先对树进行轻重链剖分,找出重儿子,在计算答案时,先遍历x的轻儿子,但不保留其影响,之后遍历x的重儿子,保留影响,最后再次遍历x的轻儿子,得到x的答案。

除了重儿子,每次遍历完后要恢复之前的状态。

CF208E

每次询问一个点x和k,问由多少个点和x由共同的k级祖先。

倍增预处理,将询问离线到x的k级祖先,用cnt数组记录当前子树内不同深度的出现次数。

inline int find(int x,int k){
    for(int i=18;~i;i--)if(k>=1<<i)k-=1<<i,x=fa[x][i];
    /* for(int i=18;~i;i--)if(k>=dep[x]-dep[fa[x][i]])k-=dep[x]-dep[fa[x][i]],x=fa[x][i];效果一样*/
    return x;
}
void dsu(int x,bool isson){
    for(int i=h[x];i;i=e[i].next){
        int y=e[i].to;
        if(y==son[x])continue;
        dsu(y,false);/*先遍历轻儿子*/
    }
    if(son[x])dsu(son[x],true);/*有重儿子则遍历重儿子*/
    for(int i=h[x];i;i=e[i].next){
        int y=e[i].to;
        if(y==son[x])continue;
        for(int j=ipt[y];j<=ipt[y]+sz[y]-1;j++)cnt[dep[mp[j]]]++;/*dfs序映射子树内节点,深度更新*/
    }
    cnt[dep[x]]++;/*更新x自己的深度*/
    for(auto a:v[x])ans[a.id]=cnt[dep[x]+a.k]-1;/*询问点的k级祖先为x,即x的k级后代为询问点,查询相同深度的点的个数并减去询问自己*/
    if(isson==false)for(int i=ipt[x];i<=ipt[x]+sz[x]-1;i++)cnt[dep[mp[i]]]--;/*复原*/
}

CF600E

每个点由颜色,求每棵子树占据主导地位的颜色的编号和。

为每个颜色开一个桶,记录当前最大值和sum,每次由更新操作时比较cnt和最大值,相等则累加sum,cnt大于最大值时更新最大值并重置sum,清除轻儿子贡献时清空最大值和sum.

void dsu(int x,bool isson){
    for(int i=h[x];i;i=e[i].next){
        int y=e[i].to;
        if(y==son[x]||y==fa[x])continue;
        dsu(y,false);
    }
    if(son[x])dsu(son[x],true);
    cnt[col[x]]++;
    if(cnt[col[x]]>ma)ma=cnt[col[x]],sum=col[x];
    else if(cnt[col[x]]==ma)sum+=col[x];
    for(int i=h[x];i;i=e[i].next){
        int y=e[i].to;
        if(y==son[x]||y==fa[x])continue;
        for(int j=ipt[y];j<=ipt[y]+sz[y]-1;j++){
            cnt[col[mp[j]]]++;
            if(cnt[col[mp[j]]]>ma)ma=cnt[col[mp[j]]],sum=col[mp[j]];
            else if(cnt[col[mp[j]]]==ma)sum+=col[mp[j]];
        }
    }
    ans[x]=sum;
    if(isson==false){
        sum=ma=0;
        for(int i=ipt[x];i<=ipt[x]+sz[x]-1;i++)cnt[col[mp[i]]]--;
    }
}

CF1709E

每个点由点权,定义一棵树合法当且仅当不存在简单路径的异或和为0,每次可以改变一个点权成为任意数,求最少操作数使得树合法。

假设将x的点权修改为$2{30+x}$,那么所有经过x的路径的异或和都不会为0。为每一个点开一个集合存子树内所有点的dis,即1到该点的异或和,枚举x的儿子y,将y的集合合并到x上面,强制x的size大于y的size,枚举y中每一个元素k,若在x中可以找到a[x]k,那么x需要修改,之后将x的集合清空。

void dfs(int x,int fa){
    mp[x][dis[x]]=true;
    bool flag=false;
    for(auto y:v[x]){
        if(y==fa)continue;
        dis[y]=dis[x]^a[y];
        dfs(y,x);
        if(mp[x].size()<mp[y].size())swap(mp[x],mp[y]);
        for(auto k:mp[y])if(mp[x].find(a[x]^k.first)!=mp[x].end()){
            flag=true;
            break;
        }
        for(auto k:mp[y])mp[x][k.first]=true;
    }
    if(flag==true)mp[x].clear(),ans++;
}

CF246E

一片森林,每个点有一个字符串作为名字,每次询问点x的k级子孙共有多少个不同的名字。

unordered_map维护同一个深度的字符串集合,撤销轻儿子操作时则清空它。

void dsu(int x,bool isson){
    for(int i=h[x];i;i=e[i].next){
        int y=e[i].to;
        if(y==son[x])continue;
        dsu(y,false);
    }
    if(son[x])dsu(son[x],true);
    for(int i=h[x];i;i=e[i].next){
        int y=e[i].to;
        if(y==son[x])continue;
        for(int j=ipt[y];j<=ipt[y]+sz[y]-1;j++)cnt[dep[mp[j]]][s[mp[j]]]=true;
    }
    cnt[dep[x]][s[x]]=true;
    for(auto a:v[x])ans[a.id]=cnt[a.x].size();
    if(isson==true)return;
    for(int i=ipt[x];i<=ipt[x]+sz[x]-1;i++)cnt[dep[mp[i]]].clear();
}
    for(int i=1;i<=m;i++){
        int x,k;
        cin>>x>>k;
        v[x].push_back({i,dep[x]+k});
    }

标签:cnt,int,sum,dsu,合并,son,启发式,树上,col
From: https://www.cnblogs.com/safeng/p/16897536.html

相关文章

  • 如何将图片转化并合并为PDF
    convert*.jpg<转换后的文件名>.pdf参考链接:https://askubuntu.com/questions/932889/libreoffice-draw-multiple-jpg-to-pdf......
  • git分支创建以及合并
    1、目前所有分支2、查看当前分支3、创建新分支gitcheckout-blogin-temp(-b创建一个分支,checkout切换到这个分支)4、gitstatus检查login-temp分支的文件状态5、......
  • git 分支合并到master,将分支所有提交汇总为一次提交
    当有一个新的功能需要开发时,我们一般需要从master新建一个功能开发分支,如果这个功能需要的开发周期超过一天,我们一般都会留下多次commit提交。当功能开发并测试完毕,需要合......
  • 树上背包(注意事项)
    第一维从大的开始枚举第二位从小的开始枚举也可以统计大小从而剪枝voiddfs(intnow){if(w2[now]>m)return;f[now][w2[now]]=v2[now];for(inti=h2[now......
  • 关于poi取消合并区域的方法-java
    //主要用于原来的excel模板已经存在合并区域、再次合并会导致合并异常privatebooleanremoveMergedRegion(Sheetsheet,CellRangeAddressmergedRegionToRemove){......
  • C语言学习--练习--合并两个字符串
    将两个字符串合并追加在一起,类似于python的str1+str2 #include<stdio.h>#include<string.h>#include<stdlib.h>//字符串追加,将两个字符串结合在一起intmain(......
  • 21. 合并两个有序链表 ----- 递归调用、链表指针
    将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  示例1:输入:l1=[1,2,4],l2=[1,3,4]输出:[1,1,2,3,4,4]示例......
  • 6.numpy数据的常用操作 数组的变形,连接合并,分裂等
      3.变形   使用reshape函数,注意参数是一个tuple!#产生0-10的随机整数arr6=np.random.randint(0,10,size=(20))arr6array([2,8,9,6,2,6,6,1......
  • (pandas)excel合并实例
    问题:合并111.xls、222.xls,最终效果如图......
  • 28、批量实现txt文件内容合并
    题目:  在many_org文件夹中有三个.txt文件,如何将三个文件的内容整理到一个文件里?思路:  1、遍历路径下的所有文件。  2、判断出.txt文件,将其所有内容保存至新列表......