问题 22220 --NOI2014湖北省选二试第2题 三叉神经树

22220: NOI2014湖北省选二试第2题 三叉神经树

时间限制: 8 Sec  内存限制: 256 MB
提交: 1  解决: 1
[提交][状态][讨论版][数据上传:][下载FPS8元][下载测试数据8元][198596kb]

题目描述

    计算神经学作为新兴的交叉学科近些年来一直是学术界的热点。一种叫做
  SHOI 的神经组织因为其和近日发现的化合物SHTSC 的密切联系引起了人们的
  极大关注。
    SHOI 组织由若干个SHOI 细胞构成,SHOI 细胞之间形成严密的树形结构。
  每个SHOI 细胞都有且只有一个输出端,被称为轴突,除了一个特殊的、被称
  为根细胞的SHOI 细胞的输出作为整个组织的输出以外,其余细胞的轴突均连
  向其上级SHOI 细胞;并且有且只有三个接收端,被称为树突,从其下级细胞
  或者其它神经组织那里接收信息。SHOI 细胞的信号机制较为简单,仅有0 和
  1 两种。每个SHOI 细胞根据三个输入端中0 和1 信号的多寡输出较多的那一种。
    现在给出了一段SHOI 组织的信息,以及外部神经组织的输入变化情况。请
  你模拟SHOI 组织的输出结果。

输入

    第一行一个整数:n。表示SHOI 组织的总细胞个数。SHOI 细胞由1~n 编
  号,编号为1 的是根细胞。
    从第二行开始的n 行,每行三个整数x1, x2, x3,分别表示编号为1~n 的
  SHOI 细胞的树突连接。1<xi≤n 表示连向编号为xi 的细胞的轴突,n<xi≤3n+1 表
  示连向编号为xi 的外界输入。输入数据保证给出的SHOI 组织是合法的且所有
  的xi 两两不同。
    接下来一行2n+1 个0/1 的整数,表示初始时的外界输入。
    第n+3 行有一个整数:q,表示总操作数。

    之后q 行每行一个整数x,表示编号为x 的外界输入发生了变化。

【数据规模】
  对于10%的数据,n, q≤1000。
  对于额外10%的数据,修改仅会将0 修改成1。
  对于额外30%的数据,输入的SHOI 形成以根为端点的一条链。
  对于100%的数据,n≤500000,q≤500000。

输出

  输出q 行每行一个整数,对应第i 次外界输入变化后的根细胞的输出。

样例输入

3
2 3 4
5 6 7
8 9 10
0 0 0 0 1 1 1
5
4
4
5
6
8

样例输出

1
0
0
1
1

提示

来源

[提交][状态]