# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1137383 | fzyzzz_z | Jail (JOI22_jail) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std; ce
using ll = long long;
void solve() {
int n;
cin >> n;
vector<vector<int>> g(n);
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y;
x--; y--;
g[x].push_back(y);
g[y].push_back(x);
}
int q;
cin >> q;
vector<pair<int, int>> ps(q);
for (auto & [l, r]: ps) {
cin >> l >> r;
l--; r--;
}
bool ans = 1;
vector<int> blocked(n, 0), ss(n, 0);
function<void(int, int)> make = [&] (int x, int p) {
ss[x] = 1;
for (auto y: g[x]) {
if (y != p && !blocked[y]) {
make(y, x);
ss[x] += ss[y];
}
}
};
function<int(int, int, int)> getc = [&] (int x, int p, int t) {
for (auto y: g[x]) {
if (ss[y] > t / 2 && p != y && !blocked[y]) {
return getc(y, x, t);
}
}
return x;
};
function<void(int, int, vector<int>&)> getcc = [&] (int x, int p, vector<int> & v) {
v.push_back(x);
for (auto y: g[x]) {
if (y != p && !blocked[y]) {
getcc(y, x, v);
}
}
};
function<void(int, vector<pair<int, int>>)> work = [&] (int root, vector<pair<int, int>> p) {
if (blocked[root] || !p.size()) return;
make(root, -1);
int c = getc(root, -1, ss[root]);
map<int, int> color;
map<int, vector<pair<int, int>>> np;
int at = 0;
vector<int> v;
for (auto y: g[c]) {
if (!blocked[y]) {
v.clear();
getcc(y, c, v);
for (auto x: v) {
color[x] = at;
}
at++;
}
}
for (auto [x, y]: p) {
if (color[x] == color[y]) {
np[color[x]].push_back({x, y});
}
}
blocked[c] = 1;
for (auto y: g[c]) {
work(y, np[color[y]]);
}
};
work(0, ps);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}