| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1143776 | monkey133 | Jail (JOI22_jail) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
//#include "includeall.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i)
#define RFOR(i, x, n) for (ll i =x; i>=n; --i)
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
typedef pair<pi, pi> piii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll n, m, lab;
vector<ll> adj[500005], adj2[5000005];
ll st[150005],fi[150005];
ll twok[5000005][25], id1[5000005][25], id2[5000005][25], dep[5000005], status[5000005];
ll kpar(ll x, ll k)
{
for (ll i=0; i<20; ++i) if ((1LL << i)&k) x = twok[x][i];
return x;
}
ll lca(ll x, ll y)
{
if (x==y) return x;
if (dep[x] < dep[y]) swap(x, y);
x = kpar(x, dep[x] - dep[y]);
if (x==y) return x;
for (ll i=19; i>=0; --i)
{
if (twok[x][i]==0 || twok[y][i]==0 || twok[x][i]==twok[y][i]) continue;
x = twok[x][i], y = twok[y][i];
}
return twok[x][0];
}
void dfs(ll x = 1, ll p = -1)
{
for (ll k=1; k<20; ++k)
{
twok[x][k] = twok[twok[x][k-1]][k-1];
id1[x][k] = ++lab;
id2[x][k] = ++lab;
// start : go up
if (id1[x][k-1] > 0) adj2[id1[x][k-1]].pb(id1[x][k]);
if (id1[twok[x][k-1]][k-1] > 0) adj2[id1[twok[x][k-1]][k-1]].pb(id1[x][k]);
// end : go down
if (id2[x][k-1] > 0) adj2[id2[x][k]].pb(id2[x][k-1]);
if (id2[twok[x][k-1]][k-1] > 0) adj2[id2[x][k]].pb(id2[twok[x][k-1]][k-1]);
}
for (ll u: adj[x]) if (u!=p)
{
dep[u] = dep[x] + 1;
twok[u][0] = x;
dfs(u, x);
}
}
void add_dir(ll from , ll to, ll idx)
{
ll k = dep[from] - dep[to] + 1;
ll now = from;
for (ll i=19; i>=0; --i) if ((1LL << i) & k)
{
if (id1[now][i]) adj2[id1[now][i]].pb(idx);
now = twok[now][i];
}
}
void add_rev(ll from , ll to, ll idx)
{
ll k = dep[from] - dep[to] + 1;
ll now = from;
for (ll i=19; i>=0; --i) if ((1LL << i) & k)
{
if (id2[now][i]) adj2[idx].pb(id2[now][i]);
now = twok[now][i];
}
}
bool fail = false;
void topo(ll node)
{
if (status[node]==2) return;
if (status[node]==1) {fail = true; return;}
status[node]=1;
for (ll x: adj2[node])
{
topo(x);
if (fail) break;
}
status[node]=2;
}
void solve()
{
cin >> n;
for (ll i=0; i<n-1; ++i)
{
ll u, v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
cin >> m;
lab = m;
for (ll i=1; i<=m; ++i)
{
cin >> st[i] >> fi[i];
id1[st[i]][0] = i;
id2[fi[i]][0] = i;
}
// decompose every path into log(n) segment + twok decomposition
dfs();
// add edges
for (ll i=1; i<=m; ++i)
{
ll lc = lca(st[i], fi[i]);
// connect to other st[i]
// *excluding st[i] -> st[i] to prevent self-loop
if (st[i]==lc) add_dir(fi[i], kpar(fi[i], dep[fi[i]] - dep[st[i]]-1), i);
else add_dir(twok[st[i]][0], lc, i), add_dir(fi[i], lc, i);
// connect to other fi[i]
if (fi[i]==lc) add_rev(st[i], kpar(st[i], dep[st[i]] - dep[fi[i]]-1), i);
else add_rev(st[i], lc, i), add_rev(twok[fi[i]][0], lc, i);
}
for (ll i=1; i<=m; ++i) topo(i);
if (fail) cout << "No\n";
else cout << "Yes\n";
for (ll i=1; i<=n; ++i) adj[i].clear(), dep[i] = 0;
for (ll i=1; i<=lab; ++i) adj2[i].clear(), status[i] = 0;
for (ll i=1; i<=lab; ++i) for (ll k=0; k<20; ++k) twok[i][k] = id1[i][k] = id2[i][k] = 0;
fail = 0;
}
int main()
{
ll q;
cin >> q;
while (q--) solve();
return 0;
}