P2720 小A的礼物

    • 35通过
    • 91提交
  • 题目提供者 _Sugar_
  • 评测方式 云端评测
  • 标签 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    数据已更新(2018-3-2)

    题目描述

    小A去学校参加活动辣,学校会发礼物哦,学校有很多礼物点

    每一个礼物点都有去别的礼物点的道路

    每一个礼物点都有各种种类的礼物

    为了防止多次领礼物,这些道路都是单向的道路,并且没有环

    而且对于每条边联接a,b点,如果删去这条边之后,存在点c可以到达a,也能到达b,那么这条边就不会存在于路径中

    并且除了点1之外,所有点有且只有一条入边

    小A想知道,对于点S能到达的所有点(包括本身),有多少种不同的礼物?

    输入输出格式

    输入格式:

    第一行是礼物点的数量n(n <= 100000)

    接下来1行n-1个数,分别代表点2...n的入点

    接下来1行n个数,代表每个节点的礼物编号

    接下来一行是m,代表询问数量

    接下来m行,每行一个节点编号,代表询问的节点编号

    输出格式:

    对于每个询问,输出礼物总数

    输入输出样例

    输入样例#1: 复制
    4
    1 2 2
    1 2 3 3
    2
    1
    2
    输出样例#1: 复制
    3
    2

    说明

    点1可以到达点1 2 3 4 有三种礼物1 2 3

    点2可以到达点2 3 4 有两种礼物2 3

    数据点编号 N M ci(颜色)

    1                 100       100          <=100
    2              1000       1000         <=1000
    3              1000       1000         <=1000
    4            10000       10000         <=20
    5            10000       10000       <=20
    6            50000       50000       <=50000
    7           100000       50000      <=60000
    8           100000       50000      <=60000
    保证1号点可到达所有点
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。