/ Vijos / 题库 /

子树结点数

子树结点数

时间限制:1秒  内存限制:256M


【问题描述】

  给出一棵含 \(N\) 个结点的无根树,结点编号为 \(1..N\),并指定根 \(root\)。请编程以 \(x\) 为根的子树的结点数目。

【输入格式】

  第 \(1\) 行一个整数是 \(N\),表示树的结点数量;
  第 \(2\sim N\) 行,每行两个正整数 \(u,v\)(\(1≤u,v≤N\)),表示结点 \(u\) 和 \(v\) 之间有一条树边;
  第 \(N+1\) 行一个整数,指定的根结点为 \(root\)
  第 \(N+2\) 行一个整数 \(m\),表示询问数
  接下来的 \(m\) 行,每行是一个整数 \(x\),表示要计算以 \(x\) 为根的子树结点数目。

【输出格式】

  共 \(m\) 行,每行一整数,表示以 \(x\) 为根的子树结点数目。

【输入输出样例】

 Input

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

 Output

3

【数据说明】

  对于 \(100\%\) 的数据 \(1≤n≤50000\)。

【来源】

  Mr.he

信息

ID
1631
难度
9
分类
树结构 点击显示
标签
(无)
递交数
1
已通过
1
通过率
100%
被复制
4
上传者