P16150 [ICPC 2017 NAIPC] Ski Resort

作为美国一家世界知名滑雪度假村的企业家，你希望通过在度假村的各个关键位置设立小吃摊来增加销售额。 该滑雪度假村建在一座山上。滑雪缆车可以将客人送到山顶。从那里，他们可以滑雪到山上的多个地点。 山上有 $n$ 个区域，编号为 $1 \dots n$。山顶是区域 1。区域之间通过严格下坡的滑雪道连接。换句话说，离开一个区域后，若不乘坐滑雪缆车，就无法返回该区域。每个区域（包括区域 1）都恰好有一个小吃摊。 作为度假村的老板，你想了解如何在小吃摊之间有效分配零食，以更好地服务客人（并赚更多的钱）。为此，你希望进行一项调查，并通过若干独立的查询来分析结果。调查中的每位客人都有一种最喜欢的零食和一个最喜欢访问的区域列表。你想知道如何最好地在小吃摊中放置他们最喜欢的零食。 每个查询包含一组客人最喜欢的区域和一个数字 $k$。你需要计算将这位客人最喜欢的零食分配到山上恰好 $k$ 个小吃摊的方案数，且需满足以下条件： 1. 对于该客人最喜欢的每个区域，从山顶到该区域的所有滑雪道路径上，恰好有一个小吃摊提供该客人最喜欢的零食（换句话说，他们不能有多个可选择的小吃摊提供该零食）。 2. 每个被分配了该客人最喜欢零食的小吃摊，必须位于从山顶到查询集中某个区域的一条滑雪道路径上。

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。输入的第一行包含三个空格分隔的整数 $n$、$m$ 和 $q$，其中 $n$（$1 \leq n \leq 10^5$）是山上的区域数量，$m$（$1 \leq m \leq n + 50$）是滑雪道的数量，$q$（$1 \leq q \leq 10^5$）是查询的数量。 接下来的 $m$ 行，每行包含两个整数 $x$ 和 $y$（$1 \leq x, y \leq n, x \neq y$），表示从区域 $x$ 到区域 $y$ 的一条滑雪道。任意两个区域之间最多有一条滑雪道。从区域 1 出发，可以通过一系列滑雪道到达每个区域。 接下来的 $q$ 行，每行是一个由空格分隔的整数序列，以 $k$ 和 $a$ 开头，后面跟着 $a$ 个整数 $i$。其中，$k$（$1 \leq k \leq 4$）表示要分配该客人最喜欢零食的小吃摊数量，$a$（$1 \leq a \leq n$）表示查询集中的区域数量，$a$ 个整数 $i$（$1 \leq i \leq n$）是查询集中区域的编号。在任意一个查询中，$i$ 的值不会重复。 所有查询中 $a$ 的总和不超过 $100{,}000$。

输出 $q$ 行，每行一个整数，表示每个查询中选择小吃摊的方案数，按输入顺序输出。如果一种配置中选择了一个区域，而另一种配置中没有选择该区域，则认为两种配置不同。

翻译由 DeepSeek V3.2 完成