销售网络问题
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
问题描述
华为公司积极开拓北美市场,首先在北美建立销售总部,总部在附近地区发展一些销售
点,这些销售点可以发展建立下一级销售点,依此类推,最终形成一个新型分级销售网络。
假设在销售网络中,有 N 个销售点(包括总部),将它们分别编号为 1 至 N。考虑到金融
危机,销售总部决定撤销一些销售点,保留其他销售点。需要注意是:
(1)如果撤销一个销售点,那么该销售点发展的所有下级销售点均要撤销,依此类推;
(2)销售总部不能撤销自己;
(3)销售总部可以不撤销任何销售点。
请你帮忙告诉华为公司:共存在多少个销售点撤销方案。
问题输入
输入包括多个行,首先给出一个整数 N,接着 N-1 行给出销售网络的建立过程,在这 N-1
行中,第 j 行(1≤j≤N-1)给出一个整数 k(i<k),表示销售点 k 发展了销售点 j。销售点
N 就是销售总部。
问题输出
输出一行,给出销售点撤销方案数。
样例输入
3
2
3
样例输出
3
提示:
样例有 3 个销售点(包括总部),“销售点 2”发展了“销售点 1”,“销售点 3”
发展了“销售点 2”,根据描述,有以下 3 种销售点撤销方案:(1)不撤销任何销售点;
(2)撤销“销售点 1”;(3)撤销“销售点 1”、“销售点 2”。
- 1 -