首页 > 其他分享 >「学习笔记」圆方树

「学习笔记」圆方树

时间：2023-08-11 22:00:29浏览次数：42  
标签：ch emplace int back 笔记 ne 学习 圆方树 tot

圆方树最初是处理「仙人掌图」（每条边在不超过一个简单环中的无向图）的一种工具，不过发掘它的更多性质，有时我们可以在一般无向图上使用它。

个人觉得，圆方树是一个很好的工具。圆方树的题目更多的侧重于想，而不是怎么建圆方树。

前置知识——点双连通分量

点双连通分量：不存在割点的图。

一个点双连通分量在圆方树上，就是一个方点，而点双连通分量中的原来的点就是圆点。方点连接着圆点，每一个点双都形成了一个菊花图，多个菊花图靠着割点连接在一起构成一棵树，或许，这就是圆方树名称的由来。

「学习笔记」双连通分量、割点与桥 - yi_fan0305 - 博客园 (cnblogs.com)

如果原图联通，则会形成一棵圆方树，否则会形成一片圆方树森林。

下面是一个图对应的点双和圆方树形态。

原图
转化
圆方树

过程

tarjan 的代码

void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++ tim;
    st.emplace_back(u);
    for (pii it : e[u]) {
        int v = it.first, i = it.second;
        if (i == fa)    continue ;
        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                ++ tot;
                int x;
                do {
                    x = st.back();
                    st.pop_back();
                    ne[x].emplace_back(tot);
                    ne[tot].emplace_back(x);
                } while (x != v);
                ne[tot].emplace_back(u);
                ne[u].emplace_back(tot);
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

其中，ne 是新图的边，e 是原图的边。

性质

  1. 不存在圆点-圆点边以及方点-方点边，即与圆点相连的边都是方点，与方点相连的边都是圆点。

  2. 圆方树一定是一棵树。

  3. 如果原图连通，构建出的圆方树也一定连通。

树具有许多良好的性质，我们可以用圆方树将仙人掌等无向图上的问题转化为树上问题。

注意

一定要开两倍空间！

由于方点的出现，点的个数肯定大于等于 \(n\)，因此，开空间时要开两倍空间。

在一些情况下（例如统计子树大小），方点不能算作是一个实点（即 siz = 0）。

题目

P4630 [APIO2018] 铁人两项 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

统计方案数，在圆方树上进行组合数计算。

//The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

const int N = 1e5 + 5;

using pii = pair<int, int>;

int n, m, tim, tot;
ll ans;
int dfn[N], low[N];
int siz1[N << 1], siz2[N << 1], fa[N << 1];
vector<pii> e[N];
vector<int> st, ne[N << 1];

void tarjan(int u, int fa) { // 找点双、建圆方树
    dfn[u] = low[u] = ++ tim;
    st.emplace_back(u);
    for (pii it : e[u]) {
        int v = it.first, i = it.second;
        if (i == fa)    continue ;
        if (! dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                int x = 0;
                ++ tot;
                do {
                    x = st.back();
                    st.pop_back();
                    ne[tot].emplace_back(x);
                    ne[x].emplace_back(tot);
                } while (x != v);
                ne[tot].emplace_back(u);
                ne[u].emplace_back(tot);
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

void dfs1(int u) { // 找以 u 为根的子树大小
    siz1[u] = (u <= n ? 1 : 0);
    for (int v : ne[u]) {
        if (v == fa[u])   continue ;
        fa[v] = u;
        dfs1(v);
        siz1[u] += siz1[v];
    }
}

void dfs2(int u) { // 更新以 u 为根的父节点及往上的节点个数（不包括 u）
    if (fa[u]) {
        siz2[u] = siz2[fa[u]] + siz1[fa[u]] - siz1[u];
    }
    for (int v : ne[u]) {
        if (v == fa[u]) continue ;
        dfs2(v);
    }
    int sum = siz1[u] + siz2[u];
    if (u <= n) {
        for (int v : ne[u]) {
            if (v == fa[u]) continue ;
            ans += (1ll * sum - siz1[v] - 1) * siz1[v];
        }
        ans += (1ll * sum - siz2[u] - 1) * siz2[u];
    } else {
        for (int v : ne[u]) {
            if (v == fa[u]) continue ;
            ans += (1ll * sum - siz1[v]) * siz1[v] * (ne[u].size() - 2); // 两个点在同一个点双中的情况
        }
        ans += (1ll * sum - siz2[u]) * siz2[u] * (ne[u].size() - 2); // 两个点有一个在点双中，要处理割点
    }
}

int main() {
    n = read<int>(), m = read<int>();
    tot = n;
    for (int i = 1, u, v; i <= m; ++ i) {
        u = read<int>(), v = read<int>();
        e[u].emplace_back(v, i);
        e[v].emplace_back(u, i);
    }
    for (int i = 1; i <= n; ++ i) {
        if (!dfn[i]) {
            tarjan(i, 0);
        }
    }
    for (int i = 1; i <= tot; ++ i) {
        if (! siz1[i]) {
            dfs1(i);
        }
    }
    for (int i = 1; i <= tot; ++ i) {
        if (! siz2[i]) {
            dfs2(i);
        }
    }
    cout << ans;
    return 0;
}

Tourists - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

每一个方点维护一个 multiset，圆方树 + 树链剖分。

//The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define mid ((l + r) >> 1)

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

using pii = pair<int, int>;

const int N = 1e5 + 5;

int n, m, q;
int tim, tot;
int dfn[N << 1], low[N];
int dep[N << 1], fa[N << 1], son[N << 1], siz[N << 1];
int tp[N << 1], pos[N << 1];
ll w[N << 1];
vector<pii> e[N];
vector<int> ne[N << 1], st;
multiset<ll> s[N];

struct seg {
    ll minn;
} t[N << 3];

seg operator + (const seg& a, const seg& b) {
    seg res;
    res.minn = min(a.minn, b.minn);
    return res;
}

inline int ls(int u) {
    return (u << 1);
}

inline int rs(int u) {
    return (u << 1 | 1);
}

void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++ tim;
    st.emplace_back(u);
    for (pii it : e[u]) {
        int v = it.first, i = it.second;
        if (i == fa)    continue ;
        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                ++ tot;
                int x;
                do {
                    x = st.back();
                    st.pop_back();
                    ne[x].emplace_back(tot);
                    ne[tot].emplace_back(x);
                } while (x != v);
                ne[tot].emplace_back(u);
                ne[u].emplace_back(tot);
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

void dfs(int u, int fat) {
    dep[u] = dep[fat] + 1;
    fa[u] = fat;
    siz[u] = 1;
    for (int v : ne[u]) {
        if (v == fat)   continue ;
        dfs(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) {
            son[u] = v;
        }
    }
}

void gettop(int u, int Top) {
    tp[u] = Top;
    dfn[u] = ++ tim;
    pos[tim] = u;
    if (! son[u])   return ;
    gettop(son[u], Top);
    for (int v : ne[u]) {
        if (v == fa[u] || v == son[u])  continue ;
        gettop(v, v);
    }
}

void build(int u, int l, int r) {
    if (l == r) {
        t[u].minn = w[pos[l]];
        return ;
    }
    build(ls(u), l, mid);
    build(rs(u), mid + 1, r);
    t[u] = t[ls(u)] + t[rs(u)];
}

void modify(int u, int l, int r, int pos, ll v) {
    if (l == r) {
        t[u].minn = v;
        return ;
    }
    if (pos <= mid) {
        modify(ls(u), l, mid, pos, v);
    } else {
        modify(rs(u), mid + 1, r, pos, v);
    }
    t[u] = t[ls(u)] + t[rs(u)];
}

void Modify(int u, ll v) {
    modify(1, 1, tot, dfn[u], v);
}

ll query(int u, int l, int r, int lr, int rr) {
    if (lr <= l && r <= rr) {
        return t[u].minn;
    }
    ll ans = 1e18, res;
    if (lr <= mid) {
        res = query(ls(u), l, mid, lr, rr);
        ans = min(ans, res);
    }
    if (rr > mid) {
        res = query(rs(u), mid + 1, r, lr, rr);
        ans = min(ans, res);
    }
    return ans;
}

ll Query(int x, int y) {
    ll ans = 1e18, res;
    while (tp[x] != tp[y]) {
        if (dep[tp[x]] < dep[tp[y]]) {
            swap(x, y);
        }
        res = query(1, 1, tot, dfn[tp[x]], dfn[x]);
        ans = min(ans, res);
        x = fa[tp[x]];
    }
    if (dep[x] > dep[y]) {
        swap(x, y);
    }
    res = query(1, 1, tot, dfn[x], dfn[y]);
    ans = min(ans, res);
    if (x > n) {
        ans = min(ans, w[fa[x]]);
    }
    return ans;
}

int main() {
    n = read<int>(), m = read<int>(), q = read<int>();
    tot = n;
    for (int i = 1; i <= n; ++ i) {
        w[i] = read<ll>();
    }
    for (int i = 1, x, y; i <= m; ++ i) {
        x = read<int>(), y = read<int>();
        e[x].emplace_back(y, i);
        e[y].emplace_back(x, i);
    }
    for (int i = 1; i <= n; ++ i) {
        if (!dfn[i]) {
            tarjan(i, 0);
        }
    }
    tim = 0;
    for (int i = 1; i <= tot; ++ i) {
        dfn[i] = 0;
    }
    dfs(1, 0);
    gettop(1, 1);
    for (int i = 2; i <= n; ++ i) {
        s[fa[i] - n].emplace(w[i]);
    }
    for (int i = n + 1; i <= tot; ++ i) {
        w[i] = (s[i - n].empty() ? 1e18 : *s[i - n].begin());
    }
    build(1, 1, tot);
    for (int i = 1, a, b; i <= q; ++ i) {
        char opt[2];
        scanf("%s", opt);
        a = read<int>(), b = read<int>();
        if (opt[0] == 'C') {
            Modify(a, b);
            if (fa[a]) {
                int fat = fa[a];
                s[fat - n].erase(s[fat - n].lower_bound(w[a]));
                s[fat - n].emplace(b);
                int minv = (*s[fa[a] - n].begin());
                if (w[fat] != minv) {
                    w[fat] = minv;
                    Modify(fat, w[fat]);
                }
            }
            w[a] = b;
        } else {
            ll ans = Query(a, b);
            cout << ans << '\n';
        }
    }
    return 0;
}

P4606 [SDOI2018] 战略游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

查找圆方树上包含所有关键点的最少点数联通块的圆点数量减去关键点的数量。

多测数据，注意清空。

//The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

using pii = pair<int, int>;

const int N = 2e5 + 5;

int T, n, m, tim, tot, q;
int dfn[N << 1], low[N], lg[N << 1];
int dep[N << 1], siz[N << 1], son[N << 1], fa[N << 1];
int dis[N << 1];
int tp[N << 1];
int sk[N << 1];
vector<pii> e[N];
vector<int> ne[N << 1], st;

void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++ tim;
    st.emplace_back(u);
    for (pii it : e[u]) {
        int v = it.first, i = it.second;
        if (i == fa)    continue ;
        if (! dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                ++ tot;
                int x;
                do {
                    x = st.back();
                    st.pop_back();
                    ne[x].emplace_back(tot);
                    ne[tot].emplace_back(x);
                } while (x != v);
                ne[tot].emplace_back(u);
                ne[u].emplace_back(tot);
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

void dfs(int u, int fat) {
    dfn[u] = ++ tim;
    siz[u] = 1;
    dis[u] = dis[fat] + (u <= n);
    fa[u] = fat;
    dep[u] = dep[fat] + 1;
    for (int v : ne[u]) {
        if (v == fat)   continue ;
        dfs(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) {
            son[u] = v;
        }
    }
}

void gettop(int u, int Top) {
    tp[u] = Top;
    if (!son[u])    return ;
    gettop(son[u], Top);
    for (int v : ne[u]) {
        if (v == fa[u] || v == son[u])  continue ;
        gettop(v, v);
    }
}

int Lca(int x, int y) {
    while (tp[x] != tp[y]) {
        if (dep[tp[x]] < dep[tp[y]]) {
            swap(x, y);
        }
        x = fa[tp[x]];
    }
    if (dep[x] > dep[y])    swap(x, y);
    return x;
}

int Dis(int x, int y) {
    return dis[x] + dis[y] - 2 * dis[Lca(x, y)];
}

void solve() {
    n = read<int>(), m = read<int>();
    tot = n;
    for (int i = 1, x, y; i <= m; ++ i) {
        x = read<int>(), y = read<int>();
        e[x].emplace_back(y, i);
        e[y].emplace_back(x, i);
    }
    for (int i = 1; i <= n; ++ i) {
        if (! dfn[i]) {
            tarjan(i, 0);
        }
    }
    for (int i = 1; i <= tot; ++ i) {
        dfn[i] = 0;
    }
    dis[1] = 0;
    dep[0] = 0;
    tim = 0;
    dfs(1, 0);
    gettop(1, 1);
    q = read<int>();
    while (q --) {
        int k = read<int>();
        for (int i = 1; i <= k; ++ i) {
            sk[i] = read<int>();
        }
        sort(sk + 1, sk + k + 1, [](int x, int y) {
            return dfn[x] < dfn[y];
        });
        int ans = 0;
        sk[k + 1] = sk[1];
        for (int i = 1; i <= k; ++ i) {
            ans += Dis(sk[i], sk[i + 1]);
        }
        ans >>= 1;
        ans -= k;
        ans += (Lca(sk[1], sk[k]) <= n);
        cout << ans;
        putchar('\n');
    }
}

void init() {
    for (int i = 0; i <= n; ++ i) {
        e[i].clear();
        low[i] = 0;
    }
    for (int i = 1; i <= tot; ++ i) {
        ne[i].clear();
        dfn[i] = 0;
        dep[i] = siz[i] = 0;
        son[i] = dis[i] = 0;
        fa[i] = sk[i] = 0;
        tp[i] = 0;
    }
    tim = 0;
    st.clear();
}

int main() {
    T = read<int>();
    while (T --) {
        solve();
        init();
    }
    return 0;
}

标签：ch,emplace,int,back,笔记,ne,学习,圆方树,tot
From： https://www.cnblogs.com/yifan0305/p/17624023.html

相关文章

  • 与点对有关的CDQ分治（菜鸟笔记）
    参考文章   首先要说明的是CDQ是一种思想，并且扩展范围很广。   这里主要说的是与点对有关的CDQ。参考文章说了与CDQ主要解决的三大类问题。第一类就是解决和点对有关的问题。主要是给定一个长度为n的序列，然后找出其中满足题意的点对\((i,j)\)。   CDQ的......
  • 七月学习之Firewalld基本介绍
    1、Firewalld基本介绍1.1、什么是Firewalld在CentOS7系统中集成了多款防火墙管理工具，默认启动的是firewalld(动态防火墙管理器)Firewalld支持CLI及GUI的两种管理方式对于接触linux较早的人员对iptables比较的熟悉由于iptables的规则比较麻烦，并且网络有一定要求，所以学习成本较高......
  • CSS基础：学习CSS样式的基本语法和应用，了解如何美化网页。
    CSS（层叠样式表）是一种用于描述网页上元素（例如文字、图像、背景等）外观和布局的样式语言。通过使用CSS，您可以控制和改变网页的外观，使其更具吸引力和易于使用。下面是一些CSS基础知识和常用的语法：选择器：CSS中的选择器用于选择要应用样式的HTML元素。最常见的选择器是元素选择器（例如......
  • JS原型链污染学习笔记
    1.JS原型和继承机制1>原型及其搜索机制NodeJS原型机制，比较官方的定义：我们创建的每个函数都有一个prototype（原型）属性，这个属性是一个指针，指向一个对象，而这个对象的用途是包含可以由特定类型的所有实例共享的属性和方法设计原型的初衷无非是对于每个实例对象，其拥有的共同......
  • openGauss学习笔记-37 openGauss 高级数据管理-事务
    openGauss学习笔记-37openGauss高级数据管理-事务事务是用户定义的一个数据库操作序列，这些操作要么全做要么全不做，是一个不可分割的工作单位。openGauss数据库支持的事务控制命令有启动、设置、提交、回滚事务。openGauss数据库支持的事务隔离级别有读已提交和可重复读。READ......
  • 学习笔记_莫比乌斯反演
    前置知识：整除分块莫比乌斯函数(\(\mu\))$\mu(d)=\begin{cases}1&(d=1)\\(-1)^{k}&\forallC_i=1\\0&\existsC_i>1\end{cases}$性质1.对于任意正整数\(n\),$$\sum_{d|n}\mu(d)=[n=1]$$[]是一个返回bool型值的判断，当[]内条件成立时返回1，否则返回0.2.对于任意......
  • wix中，传参给c#扩展的customAction的 使用笔记
    即时的CA不可回滚，但是能直接在c#里用session["属性名称"]访问上下文的属性如果是延迟执行的CA，需要通过customActionData<!--id需要一样--><CustomActionid="xxx"Execute="deferred"..../><PropertyId="xxx"Value="Arg1=111;Arg2=222;......
  • XSS基础学习
    XSS基础学习一、xss漏洞简介XSS攻击全称跨站脚本攻击，是利用网页开发时留下的漏洞，构造恶意代码植入web网站，当用户访问时，就会产生xss攻击二、xss攻击分类以及区别类型简介攻击方法区别反射型非持久化、需要用户自己点击才会触发构造钓鱼邮件主要是get类型、不和数......
  • .net core Fleck WebSocket使用笔记
    @@.netcoreFleck socket帮助类usingFleck;usingKOTL_EvidenceService.Model;usingSystem;usingSystem.Collections.Generic;namespaceKOTL_EvidenceService.Util{publicclassServerHelper{WebSocketS......
  • 【学习笔记】简单数论
    前言开个大坑。正文质数质数的个数是无限的。试除法：若一个正整数\(N\)为合数，则存在一个能整除\(N\)的数\(T\)，其中\(2\leT\le\sqrt{N}\)。时间复杂度为\(O(\sqrt{n})\)。代码实现boolisprime(intn){if(n<2)returnfalse;for(in......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99