树上移动

题面描述

小杨有一棵包含n个节点的树，其中节点的编号从1到n，每个节点的颜色要么是白色要么是黑色。小杨可以任意选择节点s和节点t并从节点s出发移动到节点 t，移动过程中小杨不能够经过重复节点。

小杨希望自己在至多经过k个黑色节点的前提下，经过的总节点数尽可能多，请你帮小杨选择经过最多的节点数是多少。

输入格式

第一行包含两个正整数n，k，代表节点数量和至多经过的黑色节点数。

第二行包含n个正整数 a1,a2,...,an，代表节点颜色，如果ai=0，代表节点颜色为白色，如果 ai=1，代表节点颜色为黑色。

之后 n-1行，每行包含两个正整数ui，vi，代表存在一条连接节点 ui和 vi的边。

输出格式

输出一个正整数，代表最多经过的节点数。

样例

排队

题目描述

小杨所在班级共有n位同学，依次以1,2，...，n标号。这n位同学想排成一行队伍，其中有些同学之间关系非常好，在队伍里需要排在相邻的位置。具体来说，有m对这样的关系（m是一个非负整数）。当m≥1时，第i对关系（1≤i≤m）给出ai，bi，表示排队时编号为ai的同学需要排在编号为bi的同学前面，并且两人在队伍中相邻。

现在小杨想知道总共有多少种排队方式。由于答案可能很大，你只需要求出答案对取模的结果。

输入格式

第一行，两个整数n，m，分别表示同学们的数量与关系数量。

接下来m行，每行两个正整数ai，bi，表示一对关系。

输出格式

一行，一个整数，表示答案对取模的结果。

样例

输入样例 1

输出样例 1

输入样例 2

输出样例 2

输入样例 3

输出样例 3

数据范围