Elearning CodePath – CTP Online Judge

BẶNG CAO ĐỒ

LEONUI

🟢 Easy #Prefix Sum #Tree #DP On Tree #Tree Traversal

### Thông tin chung

| Mục | Nội dung |
| --- | --- |
| **Tên Bài Toán** | **BẶNG CAO ĐỒ** |
| **Input** | Số nguyên dương $n$, $m$, và $2n$ số nguyên dương $x_i,y_i$ |
| **Output** | $n$ số nguyên |
| **File Input** | `LEONUI.INP` |
| **File Ouput** | `LEONUI.OUT` |

Mảnh đất CAO BẰNG - mảnh đất xinh đẹp, núi non hùng vĩ, nơi có Thác Bản, khu di tích Pác Bó,..... Và nơi đây cũng là nơi anh Đ sinh ra.

Nhiều năm về trước, anh Đ xuống Hà Nội lập nghiệp. Do ăn nên làm ra, anh rất giàu có, vàng bạc châu báu, thuốc..... điện tử rất nhiều. Năm nay, anh Đ quyết định về quê làm từ thiện.

Sơ đồ những ngọn núi trên mảnh đất Cao Bằng là sơ đồ hình cây, tức là từ bất kì ngọn núi nào, có một và chỉ một đường đi đến bất kì một ngọn núi khác qua một hoặc nhiều con đường, và các đường đi giữa hai ngọn núi là hai chiều.

Anh Đ sẽ chọn một số ngọn núi để đi từ thiện, sao cho thỏa mãn điều kiện: nếu có một ngọn núi nằm trên đường đi giữa hai ngọn núi anh muốn từ thiện thì anh cũng phải từ thiện trên ngọn núi đó, nói cách khác, từ một ngọn núi được từ thiện đến bất kì một ngọn núi được từ thiện khác thì phải tồn tại đường đi sao cho chỉ đi qua các ngọn núi đuọc từ thiện.

Anh Đ muốn nhờ bạn công việc sau: Giả sử anh chọn đỉnh $i$ làm đỉnh bắt đầu từ thiện, số cách để anh từ thiện cho một tập ngọn núi là bao nhiêu $?$

Do kết quả có thể rất lớn, Anh Đ muốn nhờ bạn tính kết quả khi modulo cho $m$.

### Định dạng đầu vào

- Dòng đầu là số nguyên dường $n$ là số ngọn núi trên Cao Bằng, $m$ là modulo.
  
  - $(1 \le n \le 10^5)$
    
  - $(2 \le m \le 10^9)$
    
- Tiếp theo là $n-1$ dòng, mỗi dòng là hai số nguyên dương $x_i, y_i$ $(1 \le x_i, y_i \le n)$ thể hiện hai ngọn núi có thể đến nhau thông qua một con đường trực tiếp.

### Định dạng đầu ra

- In ra trên $n$ dòng. Dòng thứ $i$ là số cách chọn tập ngọn núi sao cho thỏa mãn điều kiện modulo $m$.

### Ví dụ (Sample Test)

| Input (`LEONUI.INP`) | Output (`LEONUI.OUT`) |
| --- | --- |
| `4 100`  `1 2`  `1 3`  `1 4` | `8` `5` `5` `5` |

✅ Đã AC: 0 / 0 submissions