「APIO2018」铁人两项

作者:神秘网友 发布时间:2021-02-21 20:20:21

「APIO2018」铁人两项

知识点:圆方树

原题面:Loj、Luogu。

简述

给定一 \(n\) 个节点 \(m\) 条边的无向图,求存在多少对有序三元组 \((s,c,f)\),满足 \(s,c,f\) 互不相同且存在一条从 \(s\) 到 \(f\) 的简单路径使得 \(c\) 在路径上出现。
\(1\le n\le 10^5\),\(1\le m\le 2\times 10^5\)。
1S,1G。

分析

圆方树相关知识详见:「笔记」圆方树。

点双存在一个性质:对于点数 \(\ge 3\) 的点双中任意两个不同的点之间,一定存在一条简单路径经过在同一点双内的任意一点。正确性可以通过点双的定义感性理解,一种严谨的证明详见 OI-Wiki 上该题题解。

于是可以考虑建出原图的圆方树。考虑圆方树上任意两个圆点 \(x,y\) 之间的路径上的点:对于路径上某圆点 \(z\),显然原图中 \(z\) 一定在 \(x\) 到 \(y\) 的一条简单路径上,三元组 \((x,z,y)\) 对答案有贡献。对于路径上某方点,根据上述性质,方点所对应的点双中的所有节点也一定可以出现在 \(x\) 到 \(y\) 的一条简单路径上。
则对于圆方树上任意两圆点 \(s,f\),能与它们组成合法有序三元组的 \(c\) 即为圆方树上两点路径上圆点与方点维护的所有圆点并集的大小减 2(不包含 \(s,f\))。考虑到圆方树上圆点只与方点相连,方点只与圆点相连,路径上的圆点一定被路径上它们相邻的方点维护,考虑给各点赋值来方便统计。

考虑令方点权值变为代表的点双的大小,圆点的权值为 \(-1\)。圆方树上任意两圆点对答案的贡献即为路径上点权之和。问题变为统计树上所有以圆点为端点路径权值之和,转化为每个点被多少路径所包括,dfs 求解即可。总时间复杂度 \(O(n)\) 级别。

注意原图可能不连通。

代码

//知识点:圆方树
/*
By:Luckyblock
*/
#include algorithm
#include cctype
#include cstdio
#include cstring
#include vector
#include stack
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, m, e_num, val[kN], head[kN], v[kN  1], ne[kN  1];
int sumsz, dfnnum, cnt, dfn[kN], low[kN];
std::vector int newv[kN];
std::stack int st;
LL ans;
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w  3) + (w  1) + (ch ^ '0');
  return f * w;
}
void Chkmax(int fir, int sec) {
  if (sec  fir) fir = sec;
}
void Chkmin(int fir, int sec) {
  if (sec  fir) fir = sec;
}
void Add(int u_, int v_) {
  v[++ e_num] = v_, ne[e_num] = head[u_], head[u_] = e_num;
}
void Tarjan(int u_) {
  dfn[u_] = low[u_] = ++ dfnnum;
  st.push(u_);
  ++ sumsz;

  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (!dfn[v_]) {
      Tarjan(v_);
      Chkmin(low[u_], low[v_]);
      if (low[v_] = dfn[u_]) {
        val[++ cnt] = 1;
        newv[cnt].push_back(u_), newv[u_].push_back(cnt);
        while (true) {
          int top_ = st.top();
          ++ val[cnt];
          newv[cnt].push_back(top_), newv[top_].push_back(cnt);
          st.pop();
          if (top_ == v_) break; //特 别 注 意
          //u_ 与 v_ 在栈中可能不相邻,停止条件必须要写成这样
        }
      }
    } else {
      Chkmin(low[u_], dfn[v_]);
    }
  }
}
int Dfs(int u_, int fa_) {
  int sz = u_ = n;
  for (int i = 0, lim = newv[u_].size(); i  lim; ++ i) {
    int v_ = newv[u_][i];
    if (v_ == fa_) continue ;
    int ret = Dfs(v_, u_);
    ans += 2ll * sz * ret * val[u_]; //子树内的点经过 u_ 构成的路径
    sz += ret;
  }
  ans += 2ll * sz * (sumsz - sz) * val[u_]; //子树内的点与子树外的点构成的路径
  return sz;
}
//=============================================================
int main() { 
  cnt = n = read(), m = read();
  for (int i = 1; i = n; ++ i) val[i] = -1;
  for (int i = 1; i = m; ++ i) {
    int u_ = read(), v_ = read();
    Add(u_, v_), Add(v_, u_);
  }
  for (int i = 1; i = n; ++ i) { //注意原图可能不连通
    if (dfn[i]) continue ;
    sumsz = 0;
    Tarjan(i); Dfs(i, 0);
  }
  printf("%lld\n", ans);
  return 0; 
}

「APIO2018」铁人两项 相关文章

  1. 【嘉为动态】嘉为科技荣获评云计算开源产业联盟两项云管和云网类优秀案例!

    2021年1月,云计算开源产业联盟为进一步推进云计算创新与发展,因此云计算标准和开源推进委员会开展了云管和云网类优秀案例的评选活动,包括:多云管理平台(CMP)、云管理服务(MSP)、混合云、SD-WAN。 经由为期将近一个月的评审,嘉为科技从众多优异的参

  2. [BUUCTF]PWN——铁人三项(第五赛区)_2018_rop

    [BUUCTF]PWN——铁人三项(第五赛区)_2018_rop 铁人三项(第五赛区)_2018_rop[32位libc泄露] 题目附件 解题步骤: 例行检查,32位,开启了NX保护 试运行一下程序,一开始让我们输入,然后直接输出“Hellow,world” 32位ida载入,首先习惯性的shift+f12查看一下程

  3. JS排序算法

    JS排序算法 1、冒泡排序 冒泡算法是比较相邻的两项,如果前者比后者大,就交换他们。 假设一共有n项,那么一共需要n-1趟,第一趟需要交换n-1次,但是第一趟结束后,最后一项基本确定就是最大项了,所以第二次需要交换n-2次,第i次交换n-i次。 这种排序最好情

  4. 阿里达摩院公布语音AI与AI EARTH两项新进展能逼近真人语音交互也

    阿里达摩院公布语音AI与AI EARTH两项新进展:能逼近真人语音交互,也能看懂地球每一寸土地变化... “ 数据猿作为“2020云栖大会”官方受邀媒体,为大家带来了此次盛会中最精彩的报道内容。 提示: 点击文末“ 阅读原文 ”可关注数据猿最新推出的【产业图谱+

  5. 经纬恒润荣获2020年度中国汽车工业科学技术奖两项一等奖

    经纬恒润荣获2020年度“中国汽车工业科学技术奖”两项一等奖! 9月10日,由中国汽车工程学会主办的2020年度“中国汽车工业科学技术奖”终评会于江苏镇江成功召开。“中国汽车工业科学技术奖”是面向车企的重要科技奖项,被誉为中国汽车界的“诺贝尔奖”,现

  6. 喜讯|正舵者又获两项计算机软件著作权登记证书

    喜讯|正舵者又获两项计算机软件著作权登记证书 近日,由正舵者科技部开发完成的《IPFS分布式云存储V1.0》、《Filecoin区块链浏览器V1.0》两项软件通过国家版权局的最终审查,获得由中华人民共和国版权局颁发的计算机软件著作权登记证书,这是正舵者再次获得

  7. 动态 Hulu荣获两项Digiday年度视频大奖

    动态 | Hulu荣获两项Digiday年度视频大奖 — Digiday作为美国全新数字媒体,拥有100万的月活、24万的邮件订阅者、75万的社媒粉丝,专注传媒领域,生产行业观察内容,2015年被Fast Company评选为“全球传媒业十佳创新公司”。 Digiday 视频奖表彰使用视频实现

  8. 重磅DataFountain新上两项CV算法竞赛-32万巨奖等你来拿

    重磅!DataFountain新上两项CV算法竞赛-32万巨奖等你来拿! 点击 我爱计算机视觉 标星,更快获取CVML新技术 这几日,计算机视觉的算法竞赛突然冒出来许多,昨天52CV报道过今日头条新出算法大赛!短视频内容理解与推荐竞赛,不少朋友直呼玩不起,少则百万多则

  9. 浅析vue的两项原理

    浅析vue的两项原理 一.vue双向绑定原理 Vue.js-作者为中国人尤雨溪 vue实现数据双向绑定主要是:采用数据劫持结合发布者-订阅者模式的方式,通过Object.defineProperty()来劫持各个属性的setter,getter,在数据变动时发布消息给订阅者,触发相应监听回调

  10. svg高级应用及动画

    canvas 和 webGL 这两项图形技术结合 css3 可以说能完成绝大部分的动画和需求。但 canvas 和 webGL 毕竟是偏向底层的绘制引擎,某些场景使用起来还是过于繁琐的,不分场合一律使用锤子解决的行为不值得提倡。svg 在解决排版,图标,相关动画还是非常高效的,

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2020, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词