Đất nước C có \(n\) thành phố, đánh số từ \(0\) đến \(n-1\). Có \(n-1\) con đường nối các thành phố thành một cây. Đi qua một con đường tốn \(1\) đơn vị thời gian.

Mỗi thành phố còn có một cổng dịch chuyển. Dùng cổng cũng tốn \(1\) đơn vị thời gian, sau đó người dùng được đưa tới một trong \(n\) thành phố với xác suất bằng nhau. Người dùng có thể bị đưa trở lại chính thành phố hiện tại.

Có \(m\) phép thử. Trong phép thử \(i\), người thử nghiệm cần đi từ \(x_i\) tới \(y_i\). Một chiến lược phải chọn trước một hành động cho mỗi thành phố khác đích: hoặc đi tới một đỉnh kề cố định, hoặc dùng cổng dịch chuyển. Mỗi lần tới thành phố đó, người thử nghiệm luôn thực hiện hành động đã chọn.

Nói chính xác hơn, với đích \(y_i\), chiến lược là một dãy \([a_0,\ldots,a_{n-1}]\) sao cho \(a_{y_i}=-1\); với mỗi \(j\ne y_i\), hoặc \(a_j\) là một đỉnh kề \(j\), hoặc \(a_j=n\) để biểu thị việc dùng cổng. Chiến lược hợp lệ khi kỳ vọng thời gian tới đích là hữu hạn.

Với mỗi phép thử, hãy tìm kỳ vọng thời gian nhỏ nhất trong mọi chiến lược hợp lệ.

Yêu cầu cài đặt

Bạn không được cài đặt hàm main. Submission phải include teleport.h và cài đặt hàm:

std::vector<std::pair<long long, int>> teleport(
    int c, int n, int m,
    std::vector<int> u,
    std::vector<int> v,
    std::vector<int> x,
    std::vector<int> y
);

• c là số hiệu test; c = 0 biểu thị dữ liệu mẫu.
• n, m là số thành phố và số phép thử.
• Với \(0\le i<n-1\), đường thứ \(i\) nối \(u_i\) và \(v_i\).
• Với \(0\le i<m\), phép thử thứ \(i\) đi từ \(x_i\) tới \(y_i\).
• Hàm phải trả về một vector có đúng \(m\) cặp \((A_i,B_i)\). Kỳ vọng nhỏ nhất của phép thử \(i\) phải bằng phân số tối giản \(A_i/B_i\). Nếu kết quả là số nguyên dương thì phải trả về \(B_i=1\).
• Bộ chấm gọi hàm đúng một lần cho mỗi test.

Khung khai báo:

#include "teleport.h"

Dữ liệu bộ chấm

Grader đọc dữ liệu theo định dạng sau:

• Dòng đầu chứa \(c,n,m\).
• \(n-1\) dòng tiếp theo chứa các cạnh \(u_i,v_i\).
• \(m\) dòng cuối chứa các cặp \(x_i,y_i\).

Grader ghi \(m\) dòng; dòng thứ \(i\) chứa \(A_i,B_i\).

Ràng buộc

• \(2\le n\le5\cdot10^5\).
• \(1\le m\le10^6\).
• \(0\le u_i,v_i<n\) và các cạnh tạo thành một cây.
• \(0\le x_i,y_i<n\) và \(x_i\ne y_i\).

Phân nhóm

Mỗi test có giá trị \(5\) điểm.

• Tính chất A: \(u_i=i\) và \(v_i=i+1\) với mọi \(0\le i<n-1\).
• Tính chất B: \(y_i=0\) với mọi \(0\le i<m\).

Ví dụ

0 4 4
0 1
1 2
2 3
0 3
0 1
0 2
1 2

7 3
1 1
2 1
1 1

Trong phép thử đầu tiên, đi thẳng theo đường mất \(3\) đơn vị. Nếu dùng cổng tại thành phố \(0\) cho đến khi rời được thành phố này rồi đi theo đường tới \(3\), kỳ vọng là \(7/3\). Có thể chứng minh đây là giá trị nhỏ nhất.

Một chiến lược khiến người thử nghiệm đi mãi giữa hai thành phố mà không thể tới đích không hợp lệ.

Nguồn

CCF NOI 2026 - Ngày 1, bài Teleport. Đề và dữ liệu chính thức được phát hành theo giấy phép CC BY-NC.