首页 > 其他分享 >优美的暴力——树上启发式合并(dsu on tree)

优美的暴力——树上启发式合并(dsu on tree)

时间:2024-01-24 09:57:17浏览次数:43  
标签:cnt int dsu tree update tv 启发式 col es

dsu on tree

前言

在我认为,这个并不能说单独列出来成为一个算法,更恰当的说,是一种思想、技巧。反正挺简单的,也很有趣(谁会拒绝一个优美的暴力呢),所以写篇笔记记录一手。

dsu 是什么

dsu 一般指“disjoint set union”,即并查集。那么 dsu on tree 也就是指树上的合并和查询操作。

但是 dsu on tree 的实现却跟普通并查集没有太大联系。共同点仅在于功能上都能合并集合、查询。

dsu on tree 有什么用

dsu on tree 可称为树上启发式合并,是一种优美的暴力,合并子树的时候,把轻儿子合并到重儿子上去。

由于保存合并结果的是一个全局数组。所以每次计算新的字数时,都需要清空。我们可以先计算轻儿子,把重儿子留到最后,重儿子可以不用清零,直接把重儿子的信息拿去计算父亲。

这样一来,在暴力的基础上,将重儿子留到了最后,少算了一次重儿子,时间可以来到优秀的 \(O(n\log n)\)(暴力是纯粹的 \(O(n^2)\))。

从题目出发

题目:给一棵根为1的树,每次询问子树颜色种类数。

纯暴力

void update(int x, int f, int flg){
    cnt[col[x]] += flg;
    if(cnt[col[x]] == 0 && flg == -1) cols--;
    if(cnt[col[x]] == 1 && flg == 1) cols++;
    for(int i = fir[x]; i; i = es[i].nxt){
        int tv = es[i].v;
        if(tv != f) update(tv, x, flg);
    }
}

void dfs(int r, int fa){// 求子树r中的信息, fa为r的父亲
    for(int i = fir[r]; i; i = es[i].nxt){ // 遍历r的邻接点
        int tv = es[i].v;
        if(tv != fa) dfs(tv, r);
    }
    update(r, fa, 1);
    ans[r] = cols;
    update(r, fa, -1);
}

直接 \(O(n^2)\) T 飞。

当然你也可以把 dfs 写成这样(更接近 dsu 的打法):

void dfs(int r, int fa){// 求子树r中的信息, fa为r的父亲
    for(int i = fir[r]; i; i = es[i].nxt){ // 遍历r的邻接点
        int tv = es[i].v;
        if(tv != fa){
            dfs(tv, r);
            update(tv, r, -1);
        }
    }
    update(r, fa, 1);
    ans[r] = cols;
}

dsu

现在我们来优化一手暴力。先预处理出轻、重儿子,然后 dfs 轻儿子、再 dfs 重儿子。

void dfs(int x, int f){
    for(int i = fir[x]; i; i = es[i].nxt){
        int tv = es[i].v;
        if(tv != son[x] && tv != f){
            dfs(tv, x);
            update(tv, x, -1);
        }
    }
    if(son[x]) dfs(son[x], x);
    cnt[col[x]]++;
    if(cnt[col[x]] == 1) cols++;
    for(int i = fir[x]; i; i = es[i].nxt){
        int tv = es[i].v;
        if(tv != son[x] && tv != f){
            update(tv, x, 1);
        }
    }
    ans[x] = cols;
}

时间复杂度来到优秀的 \(O(n\log n)\) !!

时间复杂度分析

但是为什么呢?

因为根据轻重链划分的思想,任何一条到根的路径上,轻边不会超过 \(\log n\) 条,重链是被轻边分隔的,数量也不会超过 \(\log n\) 条。

每棵子树到父亲的边为轻边,做一次 update,最多做 \(\log n\) 次。

一次 update 可以看作是轻儿子想重儿子的合并操作。

每个节点最多合并 \(\log n\) 次,总的时间复杂度为 \(O(n\log n)\) 次。

完整代码

code

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
int n, m, ecnt, cols, col[MAXN], fir[MAXN], sz[MAXN];
int son[MAXN], cnt[MAXN], ans[MAXN];
struct edge
{
    int v, nxt;
} es[MAXN << 1];
void adde(int a, int b)
{
    es[++ecnt].v = b, es[ecnt].nxt = fir[a], fir[a] = ecnt;
    es[++ecnt].v = a, es[ecnt].nxt = fir[b], fir[b] = ecnt;
}
void dfs1(int x, int f)
{
    sz[x]++;
    int maxz = 0;
    for (int i = fir[x]; i; i = es[i].nxt)
    {
        int tv = es[i].v;
        if (tv != f)
        {
            dfs1(tv, x);
            if (sz[tv] > maxz)
                maxz = sz[tv], son[x] = tv;
            sz[x] += sz[tv];
        }
    }
}
void update(int x, int f, int flg)
{
    cnt[col[x]] += flg;
    if (cnt[col[x]] == 0 && flg == -1)
        cols--;
    if (cnt[col[x]] == 1 && flg == 1)
        cols++;
    for (int i = fir[x]; i; i = es[i].nxt)
    {
        int tv = es[i].v;
        if (tv != f)
            update(tv, x, flg);
    }
}
void dfs2(int x, int f)
{
    for (int i = fir[x]; i; i = es[i].nxt)
    {
        int tv = es[i].v;
        if (tv != son[x] && tv != f)
            dfs2(tv, x), update(tv, x, -1);
    }
    if (son[x])
        dfs2(son[x], x);
    cnt[col[x]]++;
    if (cnt[col[x]] == 1)
        cols++;
    for (int i = fir[x]; i; i = es[i].nxt)
    {
        int tv = es[i].v;
        if (tv != son[x] && tv != f)
            update(tv, x, 1);
    }
    ans[x] = cols;
}
int main()
{
    int a, b;
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        scanf("%d %d", &a, &b);
        adde(a, b);
    }
    for (int i = 1; i <= n; i++)
        scanf("%d", &col[i]);
    dfs1(1, 0);
    dfs2(1, 0);
    scanf("%d", &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d", &a);
        printf("ans: %d\n", ans[a]);
    }
    return 0;
}

Lomsat gelral

这个就是板题了,也可以线段树合并去做。但是 dsu on tree 明显更短,更好打。

code

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100025
#define LL long long int
LL sum, ans[MAXN];
int n, m, ecnt, maxcnt, col[MAXN], fir[MAXN], sz[MAXN], son[MAXN], cnt[MAXN];
struct edge
{
    int v, nxt;
} es[MAXN << 1];
void adde(int a, int b)
{
    es[++ecnt].v = b, es[ecnt].nxt = fir[a], fir[a] = ecnt;
    es[++ecnt].v = a, es[ecnt].nxt = fir[b], fir[b] = ecnt;
}
void dfs1(int x, int f)
{
    sz[x]++;
    int maxz = 0;
    for (int i = fir[x]; i; i = es[i].nxt)
    {
        int tv = es[i].v;
        if (tv != f)
        {
            dfs1(tv, x);
            if (sz[tv] > maxz)
                maxz = sz[tv], son[x] = tv;
            sz[x] += sz[tv];
        }
    }
}
void update(int x, int f, int flg)
{
    cnt[col[x]] += flg;
    if (flg == 1)
    {
        if (cnt[col[x]] > maxcnt)
            maxcnt = cnt[col[x]], sum = col[x];
        else if (cnt[col[x]] == maxcnt)
            sum += col[x];
    }
    else
        maxcnt = 0, sum = 0;
    for (int i = fir[x]; i; i = es[i].nxt)
    {
        int tv = es[i].v;
        if (tv != f)
        {
            update(tv, x, flg);
        }
    }
}
void dfs2(int x, int f)
{
    for (int i = fir[x]; i; i = es[i].nxt)
    {
        int tv = es[i].v;
        if (tv != son[x] && tv != f)
            dfs2(tv, x), update(tv, x, -1);
    }
    if (son[x])
        dfs2(son[x], x);
    cnt[col[x]]++;
    if (cnt[col[x]] > maxcnt)
        maxcnt = cnt[col[x]], sum = col[x];
    else if (cnt[col[x]] == maxcnt)
        sum += col[x];
    for (int i = fir[x]; i; i = es[i].nxt)
    {
        int tv = es[i].v;
        if (tv != son[x] && tv != f)
            update(tv, x, 1);
    }
    ans[x] = sum;
}
int main()
{
    int a, b;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &col[i]);
    for (int i = 1; i < n; i++)
        scanf("%d %d", &a, &b), adde(a, b);
    dfs1(1, 0);
    dfs2(1, 0);
    for (int i = 1; i <= n; i++)
        printf("%lld ", ans[i]);
    return 0;
}

标签:cnt,int,dsu,tree,update,tv,启发式,col,es
From: https://www.cnblogs.com/wang-holmes/p/17983950

相关文章

  • Binary tree traversal-- beadth-first and depth-first【1月23日学习笔记】
    点击查看代码//Binarytreetraversal--beadth-firstanddepth-first#include<iostream>#include<queue>//STLusingnamespacestd;structnode{intdata;node*left,*right;};node*getnewnode(intx){node*temp=newnode;temp-&......
  • Binary tree traversal-- level-order traversal using queue【1月23日学习笔记】
    点击查看代码//Binarytreetraversal--level-ordertraversalusingqueue#include<iostream>#include<queue>//STLusingnamespacestd;structnode{intdata;node*left,*right;};node*getnewnode(intx){node*temp=newnode;t......
  • Find height of a binary tree【1月23日学习笔记】
    点击查看代码#include<iostream>usingnamespacestd;structNode{intdata;Node*left,*right;};Node*newNode(intx){Node*temp=newNode;temp->data=x;temp->left=temp->right=NULL;returntemp;}voidin......
  • Inplementation of Binary Search Tree using recursion-local version 3【1月23日学
    点击查看代码#include<iostream>usingnamespacestd;structNode{intdata;Node*left,*right;//注意声明格式};Node*newNode(intx){Node*temp=newNode;temp->data=x;temp->left=temp->right=NULL;returntemp;}......
  • Inplementation of Binary Search Tree using iteration-local version 2【1月23日学
    点击查看代码#include<iostream>usingnamespacestd;structNode{intdata;Node*left;Node*right;};Node*newNode(intx){Node*temp=newNode;temp->data=x;temp->left=temp->right=nullptr;returntemp......
  • Ybt 金牌导航 6.1.F 大根堆 / BZOJ 4919 大根堆(LIS,启发式合并)
    题意简述有一个以\(1\)为根的有根树,每个点有权值\(v_i\)。你需要选出一个点集\(S\),使得点集里任意两个元素\(x,y\),若\(x\)在原树上是\(y\)的祖先,则要满足\(v_x>v_y\)。求选出的点集的最大大小是多少。解法原题限制相当于:在选出的点集构成的新树\(T\)中,每个点到根节......
  • Inplementation of Binary Search Tree【1月22日学习笔记】
    点击查看代码//InplementationofBinarySearchTree#include<iostream>usingnamespacestd;structbstnode{ intdata; bstnode*left; bstnode*right;};/*bstnode*root=NULL;*//*root=NULL;wrong*//*全局范围内的变量的初始化必须在声......
  • 使用cxTreeList创建权限管理
    设计数据库结构及内容格式如下设计界面如下,打开、保存、打印这三列Properties改为CheckBox方式显示加载菜单代码如下procedureTForm1.Button1Click(Sender:TObject);varpNode:TcxTreeListNode;//父节点RootKey:string;//根节点的键值RootNode,ChildNod......
  • treeコマンド
    tree/f>File.txt1,フォルダのみ構造表示tree2,フォルダとファイルが構造表示tree/f3,ファイルに出力したい場合はtree/f>File.txttree[:][][/f][/a]: ディレクトリ構造を表示するディスクを含むドライブを指定します。 ディレクトリ構造を表示するディレクトリを......
  • CF-570-D-启发式合并
    570-D题目大意给定一棵\(n\)个节点的树,根节点为\(1\),每个节点上有一个小写字母\(ch\)。定义节点\(x\)的深度为\(x\)到根节点的路径上的节点数量。\(q\)次询问,每次询问查询以\(x\)为根的子树之中所有深度为\(d\)的节点上字母重排之后是否可以构成一个回文串。Solution对于一组......