#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define vi vector<int>
#define ff first
#define ss second
#define pii pair<int, int>
#define pb push_back
const int MX = 120000+10;
const int MN = 25;
int n;
vi vis; // 1 is on stack, 2 is visited
int ok=1;
struct Segtree {
vector<vi> adj;
Segtree() {
adj.resize(4*n+2);
}
void add(int u, int v) {
adj[u].pb(v);
// cout<<"edge "<<u<<"->"<<v<<endl;
}
void build(int t=1, int l=1, int r=n) {
if(l==r) {
// do something with an edge
// gotta connect ID or something
return;
}
int m=(l+r)>>1;
build(t<<1, l, m); build(t<<1|1, m+1, r);
add(t, t<<1); add(t, t<<1|1);
}
void upd(int ul, int ur, int src, int t=1, int l=1, int r=n) {
// cout<<"upd "<<ul<<' '<<ur<<' '<<src<<' '<<t<<' '<<l<<' '<<r<<endl;
if(ul>r || ur<l) return;
// add edges from src to [ul, ur]
if(ul<=l && r<=ur) {
// do something
add(src, t);
return;
}
int m=(l+r)>>1;
if(ul<=m) upd(ul, ur, src, t<<1, l, m);
if(m+1<=ur) upd(ul, ur, src, t<<1|1, m+1, r);
}
void upd2(int ul, int ur, int src, int t=1, int l=1, int r=n) {
// cout<<"upd2 "<<ul<<' '<<ur<<' '<<src<<' '<<t<<' '<<l<<' '<<r<<endl;
if(ul>r || ur<l) return;
// add edges from src to [ul, ur]
if(ul<=l && r<=ur) {
// do something
add(t, src);
return;
}
int m=(l+r)>>1;
if(ul<=m) upd2(ul, ur, src, t<<1, l, m);
if(m+1<=ur) upd2(ul, ur, src, t<<1|1, m+1, r);
}
void chk(int cur, int par) {
// cout<<"chk at "<<cur<<endl;
vis[cur]=1;
for(auto x:adj[cur]) {
// cout<<cur<<"->"<<x<<endl;
if(x==par) continue;
if(vis[x]==1) {
ok=0; return;
}
if(vis[x]==0) chk(x, cur);
}
vis[cur]=2;
}
};
vi adj[MX];
// int sz[MX]; int tp[MX]; int id[MX]; int p[MX]; int dep[MX]; int di[MX];
vi sz, tp, id, p, dep, di;
vi tin, tout;
vector<vi> succ;
int tt;
int ttin=0;
void dfs1(int cur, int par) {
tin[cur]=++ttin;
p[cur]=par; sz[cur]=1;
dep[cur]=dep[par]+1;
succ[0][cur]=par;
for(auto x:adj[cur]) {
if(x==par) continue;
dfs1(x, cur);
sz[cur]+=sz[x];
}
tout[cur]=ttin;
}
void dfs2(int cur, int par, int top) {
id[cur]=++tt;
// if(id[cur]<=10) {
// cout<<"at "<<cur<<' '<<tt<<endl;
// }
di[id[cur]]=cur;
tp[cur]=top;
int mxs=-1; int mxi=-1;
for(auto x:adj[cur]) {
if(x==par) continue;
if(sz[x]>mxs) {
mxs=sz[x]; mxi=x;
}
}
if(mxi==-1) return;
dfs2(mxi, cur, top);
for(auto x:adj[cur]) {
if(x==par||x==mxi) continue;
dfs2(x, cur, x);
}
}
vector<pii> getpath(int l, int r) {
vector<pii> a,b;
while(tp[l]!=tp[r]) {
// cout<<l<<' '<<r<<endl;
if(dep[tp[l] ]>dep[tp[r]]) {
a.pb({id[tp[l]], id[l]});
l=p[tp[l]];
} else {
b.pb({id[tp[r]], id[r]});
r=p[tp[r]];
}
}
// cout<<l<<' '<<r<<endl;
a.pb({id[l], id[r]});
reverse(b.begin(), b.end());
for(auto x:b) a.pb(x);
return a;
}
int blift(int x, int d) {
// cout<<"lift node "<<x<<' '<<d<<endl;
for(int i=MN-1; i>=0; i--) {
if((d>>i)&1) {
x=succ[i][x];
}
}
return x;
}
pii trim(int x, int y) { // return path from x to y without y
// x is ancestor of y
if(tin[x]<=tin[y] && tout[y]<=tout[x]) {
return {x, p[y]};
}
// y is ancestor of x
if(tin[y]<=tin[x] && tout[x]<=tout[y]) {
// cout<<"this case"<<endl;
return {x, blift(x, dep[x]-dep[y]-1)};
}
return {x, p[y]};
}
void solve() {
tt=0; ttin=0; ok=1;
// cout<<"====="<<endl;
cin>>n;
Segtree st; st.build();
sz=vi(n+5); tp=vi(n+5); id=vi(n+5); p=vi(n+5); dep=vi(n+5); di=vi(n+5); tin=vi(n+5); tout=vi(n+5);
vis=vi(4*n+5);
succ=vector<vi>(MN, vi(n+5));
vector<pii> edges;
for(int i=0; i<=n; i++) {
adj[i].clear();
}
for(int i=0; i<n-1; i++) {
int u,v; cin>>u>>v; adj[u].pb(v); adj[v].pb(u);
}
dfs1(1, 0); dfs2(1, 0, 1);
for(int j=1; j<MN; j++) {
for(int i=1; i<=n; i++) {
succ[j][i]=succ[j-1][succ[j-1][i]];
}
}
// for(int i=1; i<=n; i++) {
// cout<<i<<": "<<id[i]<<' '<<tp[i]<<endl;
// }
int q; cin>>q;
edges.pb({-1, -1});
for(int i=1; i<=q; i++) {
// cout<<"qry number "<<i<<endl;
int x,y; cin>>x>>y; edges.pb({x,y});
// add edge from 3*n + i to [x, y]
// trim [x, y] so that it doesnt contain y?
auto [nx, ny] = trim(x,y);
// cout<<"nxny "<<nx<<' '<<ny<<endl;
vector<pii> res = getpath(nx, ny);
for(auto seg:res) {
// cout<<"seg "<<seg.ff<<' '<<seg.ss<<endl;
st.upd(min(seg.ff, seg.ss), max(seg.ff, seg.ss), 3*n+i);
}
}
// now in theory we have a graph where 3*n+i -> [segment s_i to t_i]
// now gotta connect id[x] to 3*n+x and make sure no cycles
// cout<<"almost finished building graph"<<endl;
for(int i=1; i<=q; i++) {
st.upd2(id[edges[i].ss], id[edges[i].ss], 3*n+i);
}
// now dfs to find cycles
for(int i=1; i<=q; i++) {
if(vis[3*n+i]==0) {
// cout<<"lol "<<3*n+i<<endl;
st.chk(3*n+i, 0);
}
}
if(ok) {
cout<<"Yes"<<endl;
} else {
cout<<"No"<<endl;
}
}
int32_t main() {
int t; cin>>t; while(t--) solve();
}
Compilation message
jail.cpp: In function 'void solve()':
jail.cpp:200:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
200 | auto [nx, ny] = trim(x,y);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 2 |
Correct |
1 ms |
3252 KB |
Output is correct |
| 3 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 4 |
Incorrect |
24 ms |
3660 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 2 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
3164 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 2 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
3164 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 2 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
3164 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 2 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
3164 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3160 KB |
Output is correct |
| 2 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 3 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3164 KB |
Output is correct |
| 5 |
Incorrect |
15 ms |
3380 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 2 |
Correct |
1 ms |
3252 KB |
Output is correct |
| 3 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 4 |
Incorrect |
24 ms |
3660 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
