Bước Đi Ngẫu Nhiên Trên Cây
Points
42
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một cây gồm $N$ đỉnh đánh số từ $1$ đến $N$. Có $Q$ truy vấn độc lập.
Mỗi truy vấn cho hai đỉnh $u, v$. Một quân cờ bắt đầu tại đỉnh $u$. Ở mỗi bước, nếu quân cờ chưa đứng tại $v$, nó sẽ chọn ngẫu nhiên đều một đỉnh kề với đỉnh hiện tại và di chuyển tới đó (mất $1$ bước). Khi chạm tới đỉnh $v$, quân cờ dừng lại.
Với mỗi truy vấn, hãy tính kỳ vọng số bước đi từ $u$ đến $v$, theo modulo $10^9 + 7$.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, Q$ ($1 \le N, Q \le 10^5$).
- $N - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x, y$ ($1 \le x, y \le N$) mô tả một cạnh của cây.
- $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le N$).
Dữ liệu ra
- In ra $Q$ dòng, dòng thứ $i$ chứa kết quả của truy vấn thứ $i$ theo modulo $10^9 + 7$.
Ví dụ
Input
3 2
1 2
2 3
3 1
2 2
Output
4
0
Giải thích
- Từ $3$ tới $2$ mất kỳ vọng $1$ bước; từ $2$ tới $1$ mất kỳ vọng $3$ bước, nên từ $3$ tới $1$ mất $4$ bước.
- Từ $2$ tới $2$ mất $0$ bước.
Giới hạn
- $1 \le N, Q \le 10^5$
- Thời gian: 2 giây
- Bộ nhớ: 256 MB
Community Discussion