CF893F Subtree Minimum Query

    • 67通过
    • 195提交
  • 题目来源 CodeForces 893F
  • 评测方式 RemoteJudge
  • 标签 主席树
  • 难度 NOI/NOI+/CTSC
  • 时空限制 6000ms / 512MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题目大意:

    给你一颗有根树,点有权值,m次询问,每次问你某个点的子树中距离其不超过k的点的权值的最小值。(边权均为1,点权有可能重复,k值每次询问有可能不同,强制在线

    真实询问计算方法:

    x=(x′+lans)modn+1;

    k=(k′+lans)modn;

    数据范围: n<=100000,ai<=10^9,m<=1000000

    题目描述

    You are given a rooted tree consisting of $ n $ vertices. Each vertex has a number written on it; number $ a_{i} $ is written on vertex $ i $ .

    Let's denote $ d(i,j) $ as the distance between vertices $ i $ and $ j $ in the tree (that is, the number of edges in the shortest path from $ i $ to $ j $ ). Also let's denote the $ k $ -blocked subtree of vertex $ x $ as the set of vertices $ y $ such that both these conditions are met:

    • $ x $ is an ancestor of $ y $ (every vertex is an ancestor of itself);
    • $ d(x,y)<=k $ .

    You are given $ m $ queries to the tree. $ i $ -th query is represented by two numbers $ x_{i} $ and $ k_{i} $ , and the answer to this query is the minimum value of $ a_{j} $ among such vertices $ j $ such that $ j $ belongs to $ k_{i} $ -blocked subtree of $ x_{i} $ .

    Write a program that would process these queries quickly!

    Note that the queries are given in a modified way.

    输入输出格式

    输入格式:

    The first line contains two integers $ n $ and $ r $ ( $ 1<=r<=n<=100000 $ ) — the number of vertices in the tree and the index of the root, respectively.

    The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{9} $ ) — the numbers written on the vertices.

    Then $ n-1 $ lines follow, each containing two integers $ x $ and $ y $ ( $ 1<=x,y<=n $ ) and representing an edge between vertices $ x $ and $ y $ . It is guaranteed that these edges form a tree.

    Next line contains one integer $ m $ ( $ 1<=m<=10^{6} $ ) — the number of queries to process.

    Then $ m $ lines follow, $ i $ -th line containing two numbers $ p_{i} $ and $ q_{i} $ , which can be used to restore $ i $ -th query ( $ 1<=p_{i},q_{i}<=n $ ).

    $ i $ -th query can be restored as follows:

    Let $ last $ be the answer for previous query (or $ 0 $ if $ i=1 $ ). Then $ x_{i}=((p_{i}+last)modn)+1 $ , and $ k_{i}=(q_{i}+last)modn $ .

    输出格式:

    Print $ m $ integers. $ i $ -th of them has to be equal to the answer to $ i $ -th query.

    输入输出样例

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