记录编号	329001	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016] 暗之链锁 II	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	2.346 s
提交时间	2016-10-24 19:37:20	内存使用	23.19 MiB

// 找所有附加边两端点之间在树上的路径
// 如果一条主要边被经过了0次, m条附加边随便切k条, C(m, k)
// 主要边被经过一次, 要先切掉经过它的附加边, 剩下(m-1)条切(k-1)条, C(m-1, k-1)
// 主要边被经过i次, 剩下(m-i)条切(k-i)条

#include "stdio.h"
typedef long long LL;
 
const LL maxnumber = 200100, mod = 1e9 + 7;
LL n, m, k, ans;
struct Edge
{
	LL to, next;
}edges[maxnumber << 1];
LL head[maxnumber], tot;
LL depth[maxnumber], size[maxnumber], fa[maxnumber], son[maxnumber];
LL top[maxnumber], dfn[maxnumber], id[maxnumber], dfsclock;
LL finite[maxnumber];
LL fact[maxnumber], inv[maxnumber];
 
inline void AddEdge(const LL& from, const LL& to)
{
	edges[++tot].to = to;
	edges[tot].next = head[from];
	head[from] = tot;
}
 
inline void Read(LL& a)
{
	a = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') {
		a = a * 10 + ch - '0';
		ch = getchar();
	}
}

namespace Combination
{
	inline LL GetMax(const LL& a, const LL& b)
	{
		if (a > b) return a;
		return b;
	}
	inline LL Pow(LL a, LL b)
	{
		LL ret = 1;
		for (; b; b >>= 1) {
			if (b & 1) { ret *= a; ret %= mod; }
			a *= a; a %= mod;
		}
		return ret;
	}
	LL Ex_gcd(LL a, LL b, LL& x, LL & y)
	{
		if (!b) { x = 1; y = 0; return a; }
		LL gcd = Ex_gcd(b, a%b, x, y);
		LL tmp = x; x = y; y = tmp - (a/b) * y;
		return gcd;
	}
	inline void Init()
	{
		fact[0] = 1;
		for (LL i = 1; i <= GetMax(n, m); ++i)// 注意是要取最大值
			fact[i] = fact[i-1] * i % mod;
		inv[0] = 1;
		// for (LL i = 1; i <= GetMax(n, m); ++i) {
		// 	LL y; Ex_gcd(fact[i], mod, inv[i], y);
		// 	while (inv[i] < 0) inv[i] += mod;
		// }
		for (LL i = 1; i <= GetMax(n, m); ++i)
			inv[i] = Pow(fact[i], mod-2);
	}
	inline LL C(const LL& n, const LL& m)
	{
		if (m > n) return 0;
		return fact[n] * inv[m] % mod * inv[n-m] % mod;
	}
}
 
namespace Tree_Chain_Division
{
	inline void Swap(LL& a, LL& b) { LL tmp = a; a = b; b = tmp; }

	void DFS1(const LL& a)
	{
		size[a] = 1;
		for (LL i = head[a]; i; i = edges[i].next) {
			LL to = edges[i].to;
			if (to == fa[a]) continue;
			depth[to] = depth[a] + 1;
			fa[to] = a;
			DFS1(to);
			size[a] += size[to];
			if (size[to] > size[son[a]]) son[a] = to;
		}
	}
	void DFS2(const LL& a, const LL& tp)
	{
		top[a] = tp;
		dfn[a] = ++dfsclock;
		id[dfsclock] = a;
		if (son[a]) DFS2(son[a], tp);
		for (LL i = head[a]; i; i = edges[i].next) {
			LL to = edges[i].to;
			if (to == fa[a] || to == son[a]) continue;
			DFS2(to, to);
		}
	}
	inline void Change(LL s, LL t)
	{
		LL f1 = top[s], f2 = top[t];
		while (f1 != f2) {
			if (depth[f1] < depth[f2]) { Swap(f1, f2); Swap(s, t); }
			finite[dfn[f1]]++; finite[dfn[s]+1]--;
			s = fa[f1]; f1 = top[s];
		}
		if (s == t) return;
		if (depth[s] < depth[t]) Swap(s, t);
		finite[dfn[son[t]]]++; finite[dfn[s]+1]--;
	}
}
 
#define SUBMIT
int main(int argc, char const *argv[])
{
#ifdef SUBMIT
	freopen("yamtwo.in", "r", stdin); freopen("yamtwo.out", "w", stdout);
#endif	
 
	Read(n); Read(m); Read(k);
	LL from, to, s, t;
	for (LL i = 1; i < n; ++i) {
		Read(from); Read(to);
		AddEdge(from, to);
		AddEdge(to, from);
	}
 
	depth[1] = 1;
	Tree_Chain_Division::DFS1(1);
	Tree_Chain_Division::DFS2(1, 1);
	Combination::Init();
 
	for (LL i = 1; i <= m; ++i) {
		Read(s); Read(t);
		Tree_Chain_Division::Change(s, t);
	}
 
	for (LL i = 1; i <= n; ++i)
		finite[i] += finite[i-1];
	for (LL i = 2; i <= n; ++i) {
		if (finite[i] <= k && finite[i] <= m) {
			ans += Combination::C(m-finite[i], k-finite[i]);
			ans %= mod;
		}
	}
	printf("%lld\n", ans);
 
#ifndef SUBMIT
	printf("\n----------\n");
	getchar(); getchar();
#else
	fclose(stdin); fclose(stdout);	
#endif
 
	return 0;
}