【bzoj4551】[Tjoi2016&Heoi2016]树_chentong1023的博客-程序员秘密

技术标签: --算法分类  --刷题记录  ----bzoj  ----数据结构  bzoj  --------并查集  

*题目描述:
在2016年,佳媛姐姐刚刚学习了树,非常开心。现在他想解决这样一个问题:给定一颗有根树(根为1),有以下
两种操作:1. 标记操作:对某个结点打上标记(在最开始,只有结点1有标记,其他结点均无标记,而且对于某个
结点,可以打多次标记。)2. 询问操作:询问某个结点最近的一个打了标记的祖先(这个结点本身也算自己的祖
先)你能帮帮他吗?
*输入:
输入第一行两个正整数N和Q分别表示节点个数和操作次数接下来N-1行,每行两个正整数u,v(1≤u,v≤n)表示u到v
有一条有向边接下来Q行,形如“opernum”oper为“C”时表示这是一个标记操作,oper为“Q”时表示这是一个询
问操作对于每次询问操作,1 ≤ N, Q ≤ 100000。
*输出:
输出一个正整数,表示结果
*样例输入:
5 5
1 2
1 3
2 4
2 5
Q 2
C 2
Q 2
Q 5
Q 3
*样例输出:
1
2
2
1
*题解:
我们将操作离线处理,然后从下往上做,我们用并查集来维护这棵树(森林)的形态,在读入操作时把打标记的点和它父亲断开,并且给这个点的标记数量+1。我们倒过来操作时,如果是询问,答案就是此时并查集的Find,如果是修改,就将标记-1,如果标记等于0的话就把自己和它的父亲的集合并起来,然后就做完啦。
*代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

#ifdef WIN32
    #define LL "%I64d"
#else
    #define LL "%lld"
#endif

#ifdef CT
    #define debug(...) printf(__VA_ARGS__)
    #define setfile() 
#else
    #define debug(...)
    #define filename ""
    #define setfile() freopen(filename".in", "r", stdin); freopen(filename".out", "w", stdout);
#endif

#define R register
#define getc() (S == T && (T = (S = B) + fread(B, 1, 1 << 15, stdin), S == T) ? EOF : *S++)
#define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))
#define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))
#define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0)
#define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0)
char B[1 << 15], *S = B, *T = B;
inline int FastIn()
{
    R char ch; R int cnt = 0; R bool minus = 0;
    while (ch = getc(), (ch < '0' || ch > '9') && ch != '-') ;
    ch == '-' ? minus = 1 : cnt = ch - '0';
    while (ch = getc(), ch >= '0' && ch <= '9') cnt = cnt * 10 + ch - '0';
    return minus ? -cnt : cnt;
}
#define maxn 100010
int fa[maxn], Fa[maxn], ans[maxn], cnt[maxn];
struct Poi
{
    int opt, x, id;
}qq[maxn];
inline int Find(R int x)
{
    return Fa[x] == x ? x : Fa[x] = Find(Fa[x]);
}
int main()
{
//  setfile();
    R int n = FastIn(), q = FastIn();
    Fa[1] = cnt[1] = 1;
    for (R int i = 1; i < n; ++i)
    {
        R int a = FastIn(), b = FastIn();
        fa[b] = Fa[b] = a;
    }
    R int qcnt = 0;
    for (R int i = 1; i <= q; ++i)
    {
        R char opt = getc();
        while (opt < 'A' || opt > 'Z') opt = getc();
        R int x = FastIn();
        qq[i].x = x;
        qq[i].opt = opt == 'Q';
        if (opt == 'Q') qq[i].id = ++qcnt;
        else Fa[x] = x, ++cnt[x];
    }
    for (R int i = q; i; --i)
    {
        if (qq[i].opt)
            ans[qq[i].id] = Find(qq[i].x);
        else
        {
            --cnt[qq[i].x];
            if (!cnt[qq[i].x]) Fa[qq[i].x] = fa[qq[i].x];
        }
    }
    for (R int i = 1; i <= qcnt; ++i) printf("%d\n", ans[i] );
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_33442848/article/details/51500883

智能推荐

Django's blog_Peter_Gao_的博客-程序员秘密_django project faiss

Django's bloghttps://www.cnblogs.com/DjangoBlog/分类Android(1) C++(36) java(19) linux(41) python(152) 创业园(22) 服务器(25) 架构(5) 开发工具(34) 开源项目(17) 数据库(44) 数据挖掘及机器学习(328) 搜索(15) 算法(27) 我的异...

Linux-TinyCore实践(1)_abc_714的博客-程序员秘密

今天周六,闲来无事,倒腾倒腾Linux。之前听过精简Linux,听说最小的Linux整个包可以小于2M。精简Linux系统大概有七款:    1.TinyCore,2.Puppy Linux,3.SparkyLinux,4.Lubuntu,5.Bodhi Linux,6.CrunchBang++,7.LinuxLite详细说明可以参考如下:https://www.cnbeta.com/articl...

java.lang.ClassCastException: org.apache.spark.sql.catalyst.expressions.GenericRowWithSchema cannot_w1016765655的博客-程序员秘密_genericrowwithschema

先准备构造一个DataFrame,其中scores字段是一个序列,里面的每一个元素是一个元组:import spark.implicits._val df: DataFrame = Seq( ("A", Seq(("1", 5.0), ("3", 2.0))), ("B", Seq(("1", 4.0), ("2", 5.0))), ("C", Seq(("2", 5.0), ("3", 2.0)))).toDF("userId", "scores") .cache()df.pr

Python基础(一)--初识Python_Quinto0的博客-程序员秘密

目录 Python基础(一)--初识Python1 Python基本概念1.1 什么是Python1.2 Python的语言特征1.3 Python的应用领域2 Python开发环境2.1Windows操作系统2.2Linux / Mac操作系统2.3Python虚拟环境2.4Py...

每日一条js之数组对象forEach遍历数组方法_养只猫的博客-程序员秘密_jsforeach遍历数组

方法:array.forEach(function(当前元素(必), 当前元素的索引值, 当前元素所属的数组对象), thisValue(如果这个参数为空, &quot;undefined&quot; 会传递给 &quot;this&quot;值))数组对象的forEach中有两个参数第一个是回调函数,第二个选填一般是this(这个参数目前我没用到过)回调函数中可以传入三个参数value当前参数,index索引值,当前参...

EMMC 介绍_zjuestcer的博客-程序员秘密_1.5g、 3.0g 和 6.0g emmc 速率

本文着重介绍了EMMC的硬件及软件原理,以及在手机各个启动阶段的作用和流程

随便推点

Oracle 10g 物化视图-2_cmysc40446的博客-程序员秘密

Oracle8i版本开始提供可以创建实体化视图即物化视图(MATERIALIZED VIEW),它确实存放有物理数据。物化视图包含定义视图的查询时所选择的基表中的行。对物化视图的查询就是直接从该视图中取出行。在olap环境中,m...

obs捕获窗口没有窗口_OBS 不能捕获显示屏幕和窗口怎么办?_weixin_39861920的博客-程序员秘密

OBS Studio是一款视频直播录制软件,为用户提供视频、文本、图像的捕获录制功能。OBS Studio界面简洁,功能强大,不仅录制质量好占用资源小而且还是免费的。可是安装好的OBS直播软件,不能捕获显示器或窗口的画面怎么办?显示器画面捕获不成功第一步:程序设置首先在桌面单击鼠标右键,在弹出的菜单里选择NVIDIA控制面板。打开后,在左边“3D设置”中找到“管理3D设置”,在右边单击“程序设置”...

JAVA之旅(五)——this,static,关键字,main函数,封装工具类,生成javadoc说明书,静态代码块_刘某人程序员的博客-程序员秘密_java封装main

JAVA之旅(五)——this,static,关键字,main函数,封装工具类,生成javadoc说明书,静态代码块 周末收获颇多,继续学习一.this关键字 用于区分局部变量和成员变量同名的情况 this的特点 this就代表本类对象 这在我们的set方法里面是有的 public void setName(String name) { t

JavaScript 封装自己函数库_探鱼不是鱼的博客-程序员秘密_如何将js中的函数和变量封装成库

格式// IIFE需要把匿名函数括起来,然后后边加小括号调用,当然也可以使用一元运算符~!+-等加到匿名函数前,可以省略括号// 防止其他插件没有添加末尾的分号 影响自身 ;~function (w) { /* 封账自己的函数库,为了避免过多的使用全局变量,需要使用IIFE封装. 把window对象传递进IIFE中,给全局扩展一个对象my 把所有的方法全部封装到my上,方便未来使用 */ w.my = {}; /

C语言之三位数的逆序数_生信猿人的博客-程序员秘密_逆序的三位数c语言

题目: 输入一个三位数,如123,输出结果为其逆序数,321。但是不允许出现这种情况,即输入值为120,输出值为021,正确的输出值应为21首先来思考一个问题,十进制的数字是如何表示的,这里就以三位数,123,为例。实际上,每个数位上的数字分别表示了有几个100,几个10以及几个1。那么123/100=1,即123整除100就会得到此三位数中有几个100,而整除得到的数字就是此三位数的百位数,在这里为1。如果将此三位数整除10,则得到此数有几个10,在这里为12;而后进行如此运算:12%10=2,则

vue开发百度地图开发中添加多个标注点的同时给点添加标注事件_张艺昌的博客-程序员秘密

vue开发百度地图很不兼容,如果直接循环添加事件会覆盖前面的事件,现采用网上说的一种闭包方式for(var i =0;i&lt;_this.pointArray.length;i++){ var marker1 = new BMap.Marker(new BMap.Point(_this.pointArray[i].lng,_this.pointArray[i].lat)); marker1.setLabel(new BMap.

推荐文章

热门文章

相关标签