小明正在一棵樹上數星星，這棵樹有?n?個結點?1,2,?,n。他定義樹上的一個子圖?G?是一顆星星，當且僅當?G?同時滿足：

1. G?是一棵樹。
2. G?中存在某個結點，其度數為?∣VG?∣?1。其中?∣VG?∣?表示這個子圖含有的結點數。

兩顆星星不相同當且僅當它們包含的結點集合?VG??不完全相同。小明想知道這棵樹上有多少顆不同的星星包含的結點的數量在區間?[L,R]?中，答案對?1000000007?取模。

輸入格式

輸入共?n+1?行。

第一行為一個正整數?n。

后面?n?1?行，每行兩個正整數表示樹上的一條邊。

第?n+1?行，兩個正整數?L,R。

輸出格式

輸出共?1?行，一個整數表示答案。

輸入輸出樣例

輸入 #1復制

6
1 2
1 3
2 4
2 5
3 6
3 4

輸出 #1復制

6

說明/提示

【樣例說明】

包含?3?個結點的星星有?5?個，它們的結點集合分別為?{1,2,3}，{1,2,4}，{1,2,5}，{2,4,5}，{1,3,6}。

包含?4?個結點的星星有?1?個，它的結點集合為?{1,2,4,5}。

思路：

首先要是一個子圖?G?是一棵樹，且存在一個節點的度數為?∣VG?∣?1，也就是子圖節點數量減一，顯然的，這棵樹的層數必須為?2，從另一個方面說，也就是一棵由一個節點，我們可以把它看成根，它連接了剩余?∣VG?∣?1?個節點，且剩余節點之間沒有連邊，那么我們明白了要想產生一顆星星他所需要的條件：

• 節點數量在范圍之內。

• 我們設子圖節點數量為?x，那么它的連邊數量為?x?1，這也就是樹的基本特性。

• 子圖看作一棵樹只有兩層。

• 存在一個節點使得它連向了剩余的所有節點，且剩余節點之間沒有連邊。

知道了這些就好做了，我們去遍歷一棵樹，每遍歷到一個節點，我們就去算以他為根形成滿足條件的子圖數量即可，那么怎樣計算滿足條件的子圖數量呢？現在我們設當前子圖節點數量為?x，首先我們從他給定的范圍開始，方案也就是從?x?1?個節點中選?l?個，從?x?1?個節點中選?l+1?個，從?x?1?個節點中選?l+2?個，一直到從?x?1?個節點中選?r?個，將選擇的不同數量的相應方案數相加即可，但為什么?x?要減去?1?呢？因為要去掉根，因為根是目前連接剩余?x?1?個節點的，不能算入進去。這一步，我們可以用組合數計算出，提前與處理好階乘和逆元，可以更快更方便的計算出以節點?i?為根產生的貢獻。

代碼：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
int n, in[100005], inv[100005], fec[100005], f[100005], l, r, res;
vector < int > g[100005];
int C (int x, int y)
{return inv[x] * f[y] % mod * f[x - y] % mod;
}
void dfs (int x, int fa)
{for (auto y : g[x]){if (y ^ fa)dfs(y, x);}if (static_cast<int>(g[x].size()) + 1 >= l){int p = min(r - 1ll, static_cast<int>(g[x].size()));for (int i = l - 1;i <= p; ++ i){res = (res + C(g[x].size(), i) % mod + mod) % mod;}}}
signed main()
{cin >> n;inv[0] = fec[0] = inv[1] = fec[1] = f[0] = f[1] = 1;for (register int i = 2;i <= n; ++ i){inv[i] = inv[i - 1] * i % mod;fec[i] = fec[mod % i] * (mod - mod / i) % mod;f[i] = f[i - 1] * fec[i] % mod;}for (register int i = 1;i < n; ++ i){int x, y;cin >> x >> y;g[x].push_back(y);g[y].push_back(x);}cin >> l >> r;dfs(1, 0);cout << res << "\n";return 0;
}

AC截圖：