Awesome Shawarma
시간 제한14초메모리 제한512 MB
트리가 주어질 때, 간선을 하나 추가한 뒤 다리의 개수가 [L, R]에 들어오는 서로 다른 두 노드 쌍의 수를 센다.
문제
Fouad에게는 익히지 않은 멋진 shawarma가 하나 있고, 그는 무방향 트리로 표현되는 도시에 있다. 그에게는 이 shawarma를 아주 맛있게 구워 줄 마법의 오븐이 있다는 소문이 들려 왔다. 하지만 마법의 오븐을 얻으려면 이 도시에서 두 가지 조건이 만족되어야 한다.
- 트리에서 서로 다른 두 노드를 잇도록 간선 하나를 추가로 넣는다. (이미 직접 간선으로 연결된 두 노드를 이어도 된다.)
- 새 간선을 추가한 뒤의 다리 수가 [L, R] 범위 안에 들어야 한다.
Fouad가 멋진 shawarma를 구울 마법의 오븐을 얻을 수 있도록, 위 조건을 만족하는 간선 추가 방법의 수를 세어 주자.
입력
첫 줄에는 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 줄에는 세 정수 N, L, R이 주어진다. (2 ≤ N ≤ 10^5, 0 ≤ L ≤ R ≤ N − 1) N은 노드의 수이고, L과 R은 각각 허용되는 다리 수의 최솟값과 최댓값이다.
이어서 N − 1개의 줄이 주어지고, 각 줄에는 두 정수 Xi와 Yi가 주어진다. (1 ≤ Xi, Yi ≤ N) 이는 노드 Xi와 Yi 사이의 간선을 나타낸다.
출력
각 테스트 케이스마다, 새 그래프의 다리 수가 [L, R] 범위 안에 들어가도록 새 간선 하나를 추가하는 방법의 수를 한 줄에 출력한다.
힌트
그래프의 다리란, 그 간선을 제거하면 그래프가 연결되지 않게 되는 간선을 말한다.
두 번째 예제에서 답은 서로 다른 두 노드를 아무렇게나 연결했을 때 나온다.