CF343D Water Tree

    • 183通过
    • 428提交
  • 题目来源 CodeForces 343D
  • 评测方式 RemoteJudge
  • 标签 树链剖分,树剖 线段树
  • 难度 省选/NOI-
  • 时空限制 4000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    描述 疯狂科学家Mike培养了一颗有根树,由n个节点组成。每个节点是一个要么装满水要么为空的贮水容器. 树的节点用1~n编号,其中根节点为1.对于每个节点的容器,其子节点的容器均在这一容器下方,并且每个节点都由一根可以向下流水的管道与其子节点连接. Mike想要对这棵树做以下操作:

    将节点v注满水. 这样v和其子节点都会充满水.
    将节点v置空. 这样v及其祖先节点(从v到根节点的路径)都会被置空.
    查询当前节点v是否充满水.

    初始时,所有节点都为空. Mike已经制定好了他的操作顺序. 在对树进行实验前,他决定先模拟一下操作. 请你帮助Mike得出他操作后的结果.

    输入:

    第一行为一个整数n(1<=n<=500000),为树的节点数;
    下面的n-1行为两个空格隔开的整数ai,bi(1<=ai, bi<=n),为树的边;
    下一行为一个整数q(1<=q<=500000),为操作数;接下来q行,两个空格隔开的整数ci(1<=ci<=3),vi(1<=vi<=n),其中ci为操作类型(已给出),vi为被操作的节点.
    这意味着给出的图为一棵树.

    输出:

    对于每一次操作3,如果节点v充满水,单独输出一行1,如果节点v为空,单独输出一行0. 按照操作输入的顺序输出.

    题目描述

    Mad scientist Mike has constructed a rooted tree, which consists of $ n $ vertices. Each vertex is a reservoir which can be either empty or filled with water.

    The vertices of the tree are numbered from 1 to $ n $ with the root at vertex 1. For each vertex, the reservoirs of its children are located below the reservoir of this vertex, and the vertex is connected with each of the children by a pipe through which water can flow downwards.

    Mike wants to do the following operations with the tree:

    1. Fill vertex $ v $ with water. Then $ v $ and all its children are filled with water.
    2. Empty vertex $ v $ . Then $ v $ and all its ancestors are emptied.
    3. Determine whether vertex $ v $ is filled with water at the moment.

      Initially all vertices of the tree are empty.Mike has already compiled a full list of operations that he wants to perform in order. Before experimenting with the tree Mike decided to run the list through a simulation. Help Mike determine what results will he get after performing all the operations.

    输入输出格式

    输入格式:

    The first line of the input contains an integer $ n $ ( $ 1<=n<=500000 $ ) — the number of vertices in the tree. Each of the following $ n-1 $ lines contains two space-separated numbers $ a_{i} $ , $ b_{i} $ ( $ 1<=a_{i},b_{i}<=n $ , $ a_{i}≠b_{i} $ ) — the edges of the tree.

    The next line contains a number $ q $ ( $ 1<=q<=500000 $ ) — the number of operations to perform. Each of the following $ q $ lines contains two space-separated numbers $ c_{i} $ ( $ 1<=c_{i}<=3 $ ), $ v_{i} $ ( $ 1<=v_{i}<=n $ ), where $ c_{i} $ is the operation type (according to the numbering given in the statement), and $ v_{i} $ is the vertex on which the operation is performed.

    It is guaranteed that the given graph is a tree.

    输出格式:

    For each type 3 operation print 1 on a separate line if the vertex is full, and 0 if the vertex is empty. Print the answers to queries in the order in which the queries are given in the input.

    输入输出样例

    输入样例#1: 复制
    5
    1 2
    5 1
    2 3
    4 2
    12
    1 1
    2 3
    3 1
    3 2
    3 3
    3 4
    1 2
    2 4
    3 1
    3 3
    3 4
    3 5
    
    输出样例#1: 复制
    0
    0
    0
    1
    0
    1
    0
    1
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。