#include <iostream> #include <vector> #include <algorithm> #include <queue> using namespace std; // Cấu hình giới hạn const int MAXN = 120005; const int LOG = 18; // 2^17 > 120000 const int MAX_NODES = MAXN * LOG * 2 + MAXN + 50000; const int MAX_EDGES = MAX_NODES * 4; // Biến toàn cục cho Đồ thị ban đầu (Cây) vector<int> adj[MAXN]; int up[MAXN][LOG]; int depth[MAXN]; int N, M; // Biến toàn cục cho Đồ thị phụ thuộc (Virtual Graph) // Dùng mảng tĩnh để tiết kiệm bộ nhớ và thời gian (Thay cho vector<vector>) int head[MAX_NODES], nxt[MAX_EDGES], to[MAX_EDGES]; int deg[MAX_NODES]; int edge_cnt = 0; int total_nodes = 0; void add_edge(int u, int v) { to[++edge_cnt] = v; nxt[edge_cnt] = head[u]; head[u] = edge_cnt; deg[v]++; } // DFS để dựng Binary Lifting void dfs(int u, int p, int d) { depth[u] = d; up[u][0] = p; for (int k = 1; k < LOG; ++k) { up[u][k] = up[up[u][k-1]][k-1]; } for (int v : adj[u]) { if (v != p) dfs(v, u, d + 1); } } int get_lca(int u, int v) { if (depth[u] < depth[v]) swap(u, v); for (int k = LOG - 1; k >= 0; --k) { if (depth[u] - (1 << k) >= depth[v]) u = up[u][k]; } if (u == v) return u; for (int k = LOG - 1; k >= 0; --k) { if (up[u][k] != up[v][k]) { u = up[u][k]; v = up[v][k]; } } return up[u][0]; } // Hàm lấy ID node ảo // id: 1..M (Prisoners) // SRC: M + (u-1)*LOG + k + 1 // SNK: M + N*LOG + (u-1)*LOG + k + 1 inline int ID_SRC(int u, int k) { return M + (u - 1) * LOG + k + 1; } inline int ID_SNK(int u, int k) { return M + N * LOG + (u - 1) * LOG + k + 1; } // Nối các đoạn phủ đường đi u -> ancestor vào tù nhân id // Type 0: Source (Segment -> id), Type 1: Sink (id -> Segment) void connect_path(int u, int ancestor, int id, int type) { int d = depth[u] - depth[ancestor]; // Số bước cần nhảy for (int k = LOG - 1; k >= 0; --k) { if ((d >> k) & 1) { // Đoạn (u, 2^k) if (type == 0) add_edge(ID_SRC(u, k), id); else add_edge(id, ID_SNK(u, k)); u = up[u][k]; } } } void solve() { if (!(cin >> N)) return; // Reset dữ liệu cây for (int i = 1; i <= N; ++i) adj[i].clear(); for (int i = 0; i < N - 1; ++i) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } dfs(1, 1, 0); cin >> M; vector<pair<int, int>> prisoners(M + 1); // Reset đồ thị ảo total_nodes = M + 2 * N * LOG; edge_cnt = 0; // Fill mảng head và deg cẩn thận // Vì total_nodes khá lớn, dùng vòng lặp reset thay vì memset toàn bộ mảng MAX for(int i=0; i<=total_nodes; ++i) { head[i] = 0; deg[i] = 0; } // Xây dựng khung Doubling for (int u = 1; u <= N; ++u) { for (int k = 1; k < LOG; ++k) { // Source: Con trỏ đến Cha (Gộp dòng chảy) int src_curr = ID_SRC(u, k); int src_prev = ID_SRC(u, k-1); int src_jump = ID_SRC(up[u][k-1], k-1); add_edge(src_prev, src_curr); add_edge(src_jump, src_curr); // Sink: Cha trỏ đến Con (Phân tán dòng chảy) int snk_curr = ID_SNK(u, k); int snk_prev = ID_SNK(u, k-1); int snk_jump = ID_SNK(up[u][k-1], k-1); add_edge(snk_curr, snk_prev); add_edge(snk_curr, snk_jump); } } for (int i = 1; i <= M; ++i) { int s, t; cin >> s >> t; prisoners[i] = {s, t}; // Liên kết tù nhân với vị trí cụ thể (k=0) add_edge(i, ID_SRC(s, 0)); // i đến từ S_i add_edge(ID_SNK(t, 0), i); // i đi đến T_i int lca = get_lca(s, t); // Xử lý Source (Ai đang chắn đường i?) -> Query path(S -> T) trừ S // Nhánh S -> LCA (trừ S): Nhảy lên 1 bước từ S rồi query if (s != lca) { connect_path(up[s][0], lca, i, 0); // S->LCA hướng lên add_edge(ID_SRC(lca, 0), i); // Thêm đỉnh LCA } // Nhánh T -> LCA (trừ LCA): Vì đây là đường đi của i, // và Source check là "Ai xuất phát trên đường này". // Đường đi là S->...->LCA->...->T. // Phần T->LCA thực chất là query các node từ T ngược về con của LCA. // Logic connect_path luôn query đường lên (node -> ancestor). // Đường từ LCA xuống T cũng là tập hợp các node trên đường thẳng đứng từ T lên LCA. // Ta query từ T lên con của LCA. if (t != lca) { // Query T lên LCA, nhưng LCA đã add ở trên, nên chỉ lên đến con của LCA? // Không, connect_path(T, LCA, ...) sẽ bao gồm cả LCA. // Cần cẩn thận không add trùng LCA 2 lần nếu không cần thiết (dù add trùng ko sao). // Nhưng quan trọng: path Source cover toàn bộ node trên S->T ngoại trừ S. // connect_path(T, LCA, i, 0) sẽ cover từ T lên LCA. // LCA đã được cover ở nhánh S. // Để đơn giản và tránh self-loop i->i, ta cần loại bỏ S. S nằm ở nhánh 1. // Nhánh 2 là T->LCA. Không chứa S. An toàn. connect_path(t, lca, i, 0); // Lưu ý: connect_path(u, anc) bao gồm cả u và anc. // Vậy LCA được add 2 lần. Không sao. } else { // Nếu S == LCA, đường đi là dốc xuống S -> T. // Nhánh 1 rỗng (vì bỏ S). // Nhánh 2 là T -> S. Cover path từ T lên S. // Vì bỏ S (là điểm xuất phát), ta dùng connect_path(T, S, ...) nhưng bỏ S? // connect_path phủ từ T lên S. Ta chỉ cần dừng trước S. // Nhưng hàm connect_path của mình phủ cả ancestor. // Hack nhẹ: tách node LCA ra xử lý riêng hoặc chấp nhận query dư (nhưng phải bỏ S). // Cách xử lý chính xác để BỎ S và BỎ T: // Path S -> T. // SOURCE: Cần cover (S_next -> T). // SINK: Cần cover (S -> T_prev). } } // Logic lại phần Connect Path chuẩn xác để tránh Self-Loop // Reset edge cho chắc và viết lại đoạn loop trên // (Đoạn dưới đây thay thế đoạn loop i=1..M ở trên) } // Hàm giải quyết chính xác logic path void solve_exact() { if (!(cin >> N)) return; for (int i = 1; i <= N; ++i) adj[i].clear(); for (int i = 0; i < N - 1; ++i) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } dfs(1, 1, 0); cin >> M; total_nodes = M + 2 * N * LOG; edge_cnt = 0; for(int i=0; i<=total_nodes; ++i) { head[i] = 0; deg[i] = 0; } for (int u = 1; u <= N; ++u) { for (int k = 1; k < LOG; ++k) { add_edge(ID_SRC(u, k-1), ID_SRC(u, k)); add_edge(ID_SRC(up[u][k-1], k-1), ID_SRC(u, k)); add_edge(ID_SNK(u, k), ID_SNK(u, k-1)); add_edge(ID_SNK(u, k), ID_SNK(up[u][k-1], k-1)); } } for(int i=1; i<=M; ++i){ int s, t; cin >> s >> t; // Liên kết cơ bản add_edge(i, ID_SRC(s, 0)); add_edge(ID_SNK(t, 0), i); int lca = get_lca(s, t); // 1. SOURCE Constraints (j -> i): Path S->T excluding S // Nhánh S -> LCA: Bắt đầu từ up[s][0] (để bỏ S) lên tới LCA if(s != lca) connect_path(up[s][0], lca, i, 0); // Nhánh T -> LCA: Từ T lên tới child của LCA (để tránh LCA nếu đã add, hoặc add cả LCA cũng dc) // Tuy nhiên, path từ S->T đi qua LCA. LCA không phải là S (trừ khi S=LCA). // Nếu S!=LCA, LCA đã được add ở dòng trên. // Nếu S==LCA, dòng trên không chạy. Ta cần add LCA ở dòng dưới? Không, LCA là S, phải bỏ S. // Vậy: // Nếu S != LCA: Add path(up[S], LCA). // Nhánh T: Add path(T, LCA) nhưng bỏ LCA (để tránh trùng). // Hoặc đơn giản: Add path(T, LCA). LCA bị tính 2 lần không sao. // NHƯNG nếu S=LCA, path(T, LCA) sẽ chứa LCA=S -> Sai (phải bỏ S). // Fix: // Path 1 (S hướng lên): nếu S!=LCA, connect(up[S], LCA). (Bao gồm LCA). // Path 2 (T hướng lên): connect(T, ...). // Điểm gặp nhau là LCA. // Nếu S == LCA: Cần cover toàn bộ T -> LCA ngoại trừ LCA. => connect(T, child_of_LCA_on_T_branch?). // Khó tìm child. // Đơn giản hơn: connect(T, LCA). Nếu S==LCA thì không add cạnh nối từ node ảo LCA vào i? // Không được, node ảo LCA chứa nhiều người khác. // GIẢI PHÁP TỐI ƯU: Sử dụng hàm connect_path linh hoạt (exclude ancestor) // Add SOURCE if (s != lca) { connect_path(up[s][0], lca, i, 0); // Include LCA } // Nhánh bên T: đi từ T lên LCA. // Nếu S == LCA, ta phải bỏ LCA. -> connect(T, strict_child_of_LCA). // Nếu S != LCA, ta có thể lấy cả LCA (trùng k sao). // Để tổng quát: Luôn lấy T -> LCA. // TRỪ TRƯỜNG HỢP S==LCA thì phải xử lý LCA riêng (không add). // Nhưng connect_path lại add theo đoạn. // Cách dễ nhất: Add T -> LCA. // Nếu S == LCA, ta xóa cạnh SRC(LCA, 0) -> i ? Không thể. // Ta dùng ID_SRC(u, k) -> i. // S==LCA nghĩa là i xuất phát tại LCA. // Cạnh i -> SRC(LCA, 0) đã có. // Nếu ta add SRC(LCA, ...) -> i, ta tạo chu trình. // Vậy khi add Source path cho i, ta TUYỆT ĐỐI không được đụng vào node ảo chứa S. // Node ảo (u, k) chứa S nếu u == S hoặc u là con cháu S... sai. // Node ảo (u, k) đại diện cho đoạn từ u ngược lên 2^k. // Nó chứa S nếu S nằm trong đoạn đó. // Chốt: // Nhánh S -> LCA: Đi từ up[s][0] lên LCA. (An toàn, vì đoạn này nằm trên S hẳn). // Nhánh T -> LCA: Đi từ T lên LCA. // Đoạn này chứa LCA. // Nếu S == LCA, đoạn này chứa S -> tạo chu trình. // Vậy nếu S == LCA, ta chỉ được đi từ T lên đến "con của LCA". // Để làm điều này, ta nhảy T lên đến khi depth = depth[LCA] + 1. if (depth[t] > depth[lca]) { int t_jump = t; // Nhảy t_jump lên sát LCA for(int k=LOG-1; k>=0; --k){ if(depth[t_jump] - (1<<k) > depth[lca]) t_jump = up[t_jump][k]; } // t_jump bây giờ là con trực tiếp của LCA connect_path(t, t_jump, i, 0); // Add từ T lên sát LCA // Còn bản thân LCA? // Nếu S != LCA, ta cần add LCA. (Đã add ở nhánh S->LCA). // Nếu S == LCA, ta không add LCA. // Logic này đúng hoàn toàn! } // 2. SINK Constraints (i -> j): Path S->T excluding T // Tương tự, ta cần bỏ T. // Nhánh S -> LCA: Đi từ S lên LCA. // Nếu T == LCA, phải bỏ LCA. -> Chỉ đi S lên sát LCA. if (depth[s] > depth[lca]) { int s_jump = s; for(int k=LOG-1; k>=0; --k){ if(depth[s_jump] - (1<<k) > depth[lca]) s_jump = up[s_jump][k]; } connect_path(s, s_jump, i, 1); } // Nhánh T -> LCA: Bỏ T, tức là đi từ up[T][0] lên LCA. // Nếu T != LCA: if (t != lca) { connect_path(up[t][0], lca, i, 1); // Include LCA } // Nếu T == LCA, nhánh này rỗng (đúng). Và nhánh S->LCA ở trên đã bỏ LCA (đúng). } // Topo Sort queue<int> q; for(int i=1; i<=total_nodes; ++i) { if(deg[i] == 0) q.push(i); } int processed = 0; while(!q.empty()){ int u = q.front(); q.pop(); processed++; int e = head[u]; while(e){ int v = to[e]; deg[v]--; if(deg[v] == 0) q.push(v); e = nxt[e]; } } if(processed == total_nodes) cout << "Yes\n"; else cout << "No\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int Q; if (cin >> Q) { while (Q--) solve_exact(); } return 0; }