题目描述(ID:12383)
标题: 矿洞
标签:
详情:
路面维修组在修缮地面的时候发现了一个大坑!啊哈沃德随即派人进去勘查,发现居然是一个天然矿洞!
    为了开发矿洞里的资源,啊哈沃德派人探清了矿洞的状态。矿洞类似于一棵树,所有更深层的矿洞只会与一个上层矿洞连通,而且不会与同一层次的矿洞连通。整个矿洞只有一个入口,也就是路面维修组发现的那个。啊哈沃德将矿洞中有比较大的空间的部分记为节点。矿洞一共有N个节点。
为了提高勘探效率,勘探组决定除了建立一个地面上的工作中心以外,为了方便地下工作人员以及保证他们的安全,矿洞每一个节点都要驻扎一些人手,可以是指挥部、保卫处或者工程部的人。为了便于管理,每个节点只驻扎一个部门的人。同时为了更好的保护地下人员以及提高地下的管理效率,任何两个相邻的节点不会驻扎同一部门的人。
在正式开始部署人员前,已经有工作人员下到地下了。指挥部决定对于先下去的人直接将他所在的节点分配给他所在的部门。经统计,有P个节点被预先分配了。啊哈沃德想找出一个合法的方案,英菲妮特更好奇会有多少合法的方案。啊哈沃德的问题自有人去解决,你只用解决后一个。
输入格式:
第一行给出两个整数N、P。
接下来N-1行,每行给出两个整数,表示两个节点连通。
接下来P行,每行给出两个整数s和c,表示s号节点提前被分配给c类人员。
			 C取值1、2或3,分别代表指挥部、保卫处和工程部。
输出格式:
1个整数,表示一共有几个染色方案。方案数可能较大,输出方案数mod〖10〗^9+7的值。
限制: 对 100% 的输入数据 :1<=N<=100000
样例:

输入

4 1
1 2
1 3
1 4
4 3

输出

8
登录并解答