#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define sz(v) int((v).size())
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
int mod = 1e9+7;
ll modulo(ll a) {
return ((a % mod) + mod) % mod;
}
ll add(ll a, ll b) {
return modulo(a + b);
}
ll mult(ll a, ll b) {
return modulo(a * b);
}
ll binpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b&1) {
res = mult(res, a);
}
a = mult(a, a);
b >>= 1;
}
return res;
}
const int N = 120007;
struct query {
char type;
vector <int> inds;
};
vector <pii> graph[N];
int tin[N], tout[N], timer, up[N][20];
int n, k;
int cur_pos;
int parent[N], depth[N], heavy[N], head[N], pos[N];
int tree[N*4][3];
// 0 - edge max, 1 - edge min, 2 - time max
void update(int v, int l, int r, int pos, int val, int i) {
if (l == r) {
tree[v][i] = val;
return;
}
int mid = (l+r) >> 1;
if (pos <= mid) update(v*2, l, mid, pos, val, i);
else update(v*2+1, mid+1, r, pos, val, i);
tree[v][0] = max(tree[v*2][0], tree[v*2+1][0]);
tree[v][1] = min(tree[v*2][1], tree[v*2+1][1]);
tree[v][2] = max(tree[v*2][2], tree[v*2+1][2]);
}
int get(int v, int l, int r, int ql, int qr, int i) {
if (ql > r || l > qr) return (i == 1 ? 2e9 : -2e9);
if (ql <= l && r <= qr) return tree[v][i];
int mid = (l+r) >> 1;
if (i == 1) return min(get(v*2, l, mid, ql, qr, i), get(v*2+1, mid+1, r, ql, qr, i));
else return max(get(v*2, l, mid, ql, qr, i), get(v*2+1, mid+1, r, ql, qr, i));
}
bool upper(int a, int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int get_lca(int a, int b) {
if (upper(a, b)) return a;
if (upper(b, a)) return b;
for (int i = 19; i >= 0; i--) {
if (!upper(up[a][i], b)) {
a = up[a][i];
}
}
return up[a][0];
}
int dfs(int v, int p) {
tin[v] = ++timer;
up[v][0] = p;
for (int i = 1; i < 20; i++) {
up[v][i] = up[up[v][i-1]][i-1];
}
int saizu = 1;
int max_saizu = 0;
for (auto x : graph[v]) {
auto to = x.first;
if (to == p) {
continue;
}
depth[to] = depth[v] + 1;
parent[to] = x.second;
auto tmp = dfs(to, v);
saizu += tmp;
if (tmp > max_saizu) {
max_saizu = tmp;
heavy[v] = to;
}
}
tout[v] = ++timer;
return saizu;
}
void decompose(int v, int h) {
head[v] = h; pos[v] = ++cur_pos;
if (heavy[v]) {
decompose(heavy[v], h);
}
for (auto to : graph[v]) {
if (to.first != up[v][0] && to.first != heavy[v]) {
decompose(to.first, to.first);
}
}
}
int get(int a, int b, int i) {
int res = 0;
for (; head[a] != head[b]; b = up[head[b]][0]) {
if (depth[head[a]] > depth[head[b]]) swap(a, b);
res = max(res, get(1, 1, n, pos[head[b]], pos[b], i));
}
if (depth[a] > depth[b]) swap(a, b);
return max(res, get(1, 1, n, pos[a], pos[b], i));
}
void init() {
dfs(1, 1);
decompose(1, 1);
}
int get_anc(int n, int x) {
for (int bit = 0; bit < 20; bit++) {
if (x & (1 << bit)) {
n = up[n][bit];
}
}
return n;
}
void solve() {
cin >> n >> k;
int edges = 0;
vector <query> q;
for (int i = 0; i < n+k-1; i++) {
query tmp;
cin >> tmp.type;
if (tmp.type == 'C') {
int a;
cin >> a;
tmp.inds.pb(a);
}
else {
int a, b;
cin >> a >> b;
tmp.inds.pb(a);
tmp.inds.pb(b);
if (tmp.type == 'S') {
edges++;
graph[a].pb(mp(b, edges));
graph[b].pb(mp(a, edges));
}
}
q.pb(tmp);
}
init();
for (int i = 1; i <= n; i++) {
update(1, 1, n, pos[i], parent[i], 2);
if (depth[i] == 1) {
update(1, 1, n, pos[i], parent[i], 0);
update(1, 1, n, pos[i], -parent[i], 1);
}
else if (depth[i] > 1) {
int val = parent[i]-parent[up[i][0]];
update(1, 1, n, pos[i], val, 0);
update(1, 1, n, pos[i], val, 1);
}
}
edges = 0;
for (int i = 0; i < n+k-1; i++) {
if (q[i].type == 'S') {
edges++;
}
else if (q[i].type == 'Q') {
int a = q[i].inds[1];
int b = q[i].inds[0];
int lca = get_lca(a, b);
int val_lca0 = get(lca, lca, 0), val_lca1 = get(lca, lca, 1), time_lca = get(lca, lca, 2);
//~ cout << a << ' ' << b << endl;
//~ cout << lca << endl;
update(1, 1, n, pos[lca], 0, 0);
update(1, 1, n, pos[lca], 0, 1);
update(1, 1, n, pos[lca], 0, 2);
if (a == lca) {
int B = get_anc(b, depth[b]-depth[a]-1);
int val_B0 = get(B, B, 0), val_B1 = get(B, B, 1);
update(1, 1, n, pos[B], 0, 0);
update(1, 1, n, pos[B], 0, 1);
auto res = get(a, b, 1), time = get(a, b, 2);
if (res >= 0 && time <= edges) {
cout << "yes" << endl;
}
else {
cout << "no" << endl;
}
update(1, 1, n, pos[B], val_B0, 0);
update(1, 1, n, pos[B], val_B1, 1);
}
else if (b == lca) {
int A = get_anc(a, depth[a]-depth[b]-1);
int val_A0 = get(A, A, 0), val_A1 = get(A, A, 1);
update(1, 1, n, pos[A], 0, 0);
update(1, 1, n, pos[A], 0, 1);
auto res = get(a, b, 0), time = get(a, b, 2);
if (res <= 0 && time <= edges) {
cout << "yes" << endl;
}
else {
cout << "no" << endl;
}
update(1, 1, n, pos[A], val_A0, 0);
update(1, 1, n, pos[A], val_A1, 1);
}
else {
int A = get_anc(a, depth[a]-depth[lca]-1);
int val_A0 = get(A, A, 0), val_A1 = get(A, A, 1);
int B = get_anc(b, depth[b]-depth[lca]-1);
int val_B0 = get(B, B, 0), val_B1 = get(B, B, 1);
update(1, 1, n, pos[A], -parent[A]+parent[B], 0);
update(1, 1, n, pos[A], -parent[A]+parent[B], 1);
update(1, 1, n, pos[B], -parent[B]+parent[A], 0);
update(1, 1, n, pos[B], -parent[B]+parent[A], 1);
//~ cout << a << ' ' << b << endl;
//~ cout << A << ' ' << B << endl;
//~ cout << parent[A] << ' ' << parent[B] << endl;
//~ cout << lca << endl;
auto res_max = get(b, lca, 1), res_min = get(lca, a, 0), time = get(a, b, 2);
//~ cout << res_max << ' ' << res_min << ' ' << time << endl;
if (res_min >= 0 && res_max <= 0 && time <= edges) {
cout << "yes" << endl;
}
else {
cout << "no" << endl;
}
update(1, 1, n, pos[B], val_B0, 0);
update(1, 1, n, pos[B], val_B1, 1);
update(1, 1, n, pos[A], val_A0, 0);
update(1, 1, n, pos[A], val_A1, 1);
}
update(1, 1, n, pos[lca], val_lca0, 0);
update(1, 1, n, pos[lca], val_lca1, 1);
update(1, 1, n, pos[lca], time_lca, 2);
}
else {
cout << 1 << endl;
}
}
}
int main() {
do_not_disturb
int t = 1;
//~ cin >> t;
while (t--) {
solve();
}
return 0;
}
/*
4 4
S 1 2
S 1 3
S 3 4
Q 2 1
Q 2 2
Q 2 3
Q 2 4
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
197 ms |
11876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
197 ms |
11876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
214 ms |
11972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
214 ms |
11972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
156 ms |
11860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
156 ms |
11860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
233 ms |
11900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
233 ms |
11900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
156 ms |
11928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
156 ms |
11928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
202 ms |
11884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
202 ms |
11884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
