子树结点数
时间限制: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