#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
struct dsu{
vector<int> sz, m, p;
int n; bool t;
dsu(int ns, bool ts){
n = ns; t = ts;
p.resize(n + 1);
sz.resize(n + 1);
m.resize(n + 1);
for (int i = 1; i <= n; i++){
p[i] = m[i] = i;
sz[i] = 1;
}
}
int get(int v){
if (p[v] != v){
p[v] = get(p[v]);
}
return p[v];
}
int f(int x, int y){
if (t) return max(x, y);
return min(x, y);
}
int q(int v){
return m[get(v)];
}
void unite(int x, int y){
x = get(x); y = get(y);
if (x == y) return;
if (sz[x] > sz[y]) swap(x, y);
p[x] = y;
sz[y] += sz[x];
m[y] = f(m[y], m[x]);
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
struct query{
char t;
int x, y;
};
int n, q; cin>>n>>q;
q += (n - 1);
vector<query> qs(q + 1);
vector<int> g[n + 1];
for (int i = 1; i <= q; i++){
cin>>qs[i].t>>qs[i].x;
if (qs[i].t != 'C') cin>>qs[i].y;
if (qs[i].t == 'S'){
g[qs[i].x].pb(qs[i].y);
g[qs[i].y].pb(qs[i].x);
}
}
vector<int> sz(n + 1), d(n + 1), h(n + 1), p(n + 1);
function<void(int, int)> dfs = [&](int v, int pr){
p[v] = pr;
sz[v] = 1;
for (int i: g[v]){
if (i == pr) continue;
d[i] = d[v] + 1;
dfs(i, v);
if (sz[i] > sz[h[v]]){
h[v] = i;
}
sz[v] += sz[i];
}
};
dfs(1, 0);
vector<int> head(n + 1), pos(n + 1);
int timer = 0;
function<void(int, int)> dfs_hld = [&](int v, int k){
head[v] = k;
pos[v] = ++timer;
if (!h[v]) return;
dfs_hld(h[v], k);
for (int i: g[v]){
if (pos[i]) continue;
dfs_hld(i, i);
}
};
dfs_hld(1, 1);
auto pr = [&](int a, int b){
return (d[a] > d[b]) ? a : b;
};
vector<int> f(n + 1);
dsu T1(n, 1), T2(n, 0);
auto upd = [&](int a, int b, int i){
int v = pos[pr(a, b)];
f[v] = i;
if (f[v - 1] && f[v - 1] < f[v]) T1.unite(v, v - 1);
if (v != n && f[v] < f[v + 1]) T1.unite(v, v + 1);
if (f[v - 1] > f[v]) T2.unite(v - 1, v);
if (v != n && f[v + 1] && f[v] > f[v + 1]) T2.unite(v, v + 1);
};
auto lca = [&](int x, int y){
while (head[x] != head[y]){
if (d[head[x]] > d[head[y]]){
swap(x, y);
}
y = p[head[y]];
}
return ((d[x] > d[y]) ? y : x);
};
auto check = [&](int x, int y){
int a = lca(x, y), pre = q + 1;
while (true){
// xl > ... > xr
if (d[head[x]] > d[a]){
int l = pos[head[x]], r = pos[x];
if (T2.q(r) > l || f[l] > pre) return 0;
x = p[head[x]];
pre = f[l];
}
else {
int l = pos[a] + 1, r = pos[x];
if (l <= r && (T2.q(r) > l || f[l] > pre)) return 0;
if (l <= r) pre = f[l];
break;
}
}
if (pre > q) pre = 0;
vector<pii> all;
while (true){
// xl < ... < xr
if (d[head[y]] > d[a]){
int l = pos[head[y]], r = pos[y];
all.pb({l, r});
y = p[head[y]];
}
else {
int l = pos[a] + 1, r = pos[y];
if (l <= r) all.pb({l, r});
break;
}
}
reverse(all.begin(), all.end());
for (auto [l, r]: all){
if (T1.q(l) < r || f[r] < pre) return 0;
pre = f[r];
}
return 1;
};
for (int i = 1; i <= q; i++){
if (qs[i].t == 'S'){
upd(qs[i].x, qs[i].y, i);
}
else if (qs[i].t == 'Q'){
int a = qs[i].x, b = qs[i].y;
cout<<(check(b, a) ? "yes" : "no")<<"\n";
// b -> a
}
else {
cout<<0<<"\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
2908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
2908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
3156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
3156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
2908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
2908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
3160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
3160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
2908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
2908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
2908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
2908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
