//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <set>
//#include <ext/pb_ds/assoc_contatiner.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
void debug() {cout << endl;}
template<class T, class ... U> void debug(T a, U ... b) { cout << a << " ";debug(b...);}
template<class T> void pary (T l, T r) {
while (l != r) cout << (*l) << " ", l++;
cout << endl;
}
#define ll long long
#define maxn 120005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<pii> adj[maxn];
struct query{
int ti, id, to;
query() {ti = 0, id = 0, to = 0;}
query(int x, int y, int z) {ti = x, id = y, to = z;}
};
vector<query> que[maxn];
int qtype[maxn], ans[maxn];
struct BIT{
int bit[maxn];
void modify(int ind, int val) {
for (;ind < maxn;ind += ind & (-ind)) bit[ind] += val;
}
int query(int ind) {
int ret = 0;
for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
return ret;
}
} bit;
int siz[maxn];
bool mark[maxn];
int found[maxn];
void dfs(int n, int par) {
siz[n] = 1;
for (auto v:adj[n]) {
if (v.ff != par && mark[v.ff]) {
dfs(v.ff, n);
siz[n] += siz[v.ff];
}
}
}
int get_centroid(int n, int par, int tot) {
for (auto v:adj[n]) {
if (v.ff != par && mark[v.ff]) {
if (2 * siz[v.ff] >= tot) return get_centroid(v.ff, n, tot);
}
}
return n;
}
void get_node(int n, int par, int w, vector<pii> & ret, int dir) {
ret.push_back({n, w});
for (auto v:adj[n]) {
if (v.ff != par && mark[v.ff] && (dir == 2 ? true : (dir ? v.ss > w : v.ss < w))) {
get_node(v.ff, n, v.ss, ret, dir);
}
}
}
void recur(int n, int par, vector<int> & ret) {
ret.push_back(n);
for (auto v:adj[n]) {
if (v.ff != par && mark[v.ff]) {
recur(v.ff, n, ret);
}
}
}
void solve(vector<int> a) {
//debug(49);
//pary(a.begin(), a.end());
for (int i:a) mark[i] = 1;
dfs(a[0], 0);
vector<pii> op;
int cent = get_centroid(a[0], 0, a.size());
//debug(cent);
sort(adj[cent].begin(), adj[cent].end(), [&](pii x, pii y) {return x.ss > y.ss;});
for (auto v:adj[cent]) {
if (!mark[v.ff]) continue;
vector<pii> se;
get_node(v.ff, cent, v.ss, se, 0);
for (auto node:se) {
//debug(7122, node.ff);
for (auto q:que[node.ff]) {
if (q.to == 0) {
ans[q.id] += bit.query(q.ti) + 1;
} else if (mark[q.to]) {
if (q.to != cent) ans[q.id] = (found[q.to] && found[q.to] <= q.ti);
else ans[q.id] = v.ss <= q.ti;
}
}
}
se.clear();
get_node(v.ff, cent, v.ss, se, 1);
for (auto node:se) {
//debug(2217, node.ff);
found[node.ff] = node.ss;
bit.modify(node.ss, 1);
}
op.insert(op.end(), se.begin(), se.end());
}
for (auto q:que[cent]) {
if (q.to == 0) {
ans[q.id] += 1 + bit.query(q.ti);
} else if (mark[q.to]){
if (q.to == cent) ans[q.id] = 1;
else ans[q.id] = found[q.to] && found[q.to] <= q.ti;
}
}
for (auto i:op) {
found[i.ff] = 0;
bit.modify(i.ss, -1);
}
vector<vector<int> > rec;
for (auto v:adj[cent]) {
if (!mark[v.ff]) continue;
vector<int> add;
recur(v.ff, cent, add);
rec.push_back(add);
}
for (int i:a) mark[i] = 0;
for (auto i:rec) solve(i);
}
int main() {
io
int n, k;
cin >> n >> k;
int cur = 1, qcnt = 0, tc = 0;
for (int i = 0;i < n + k - 1;i++) {
char type;
cin >> type;
if (type == 'S') {
int a, b;
cin >> a >> b;
adj[a].push_back({b, cur});
adj[b].push_back({a, cur});
cur++;
} else if (type == 'Q') {
int a, b;
cin >> a >> b;
qtype[qcnt] = 0;
que[b].push_back(query(cur - 1, qcnt++, a));
} else {
int d;
cin >> d;
qtype[qcnt] = 1;
tc++;
que[d].push_back(query(cur - 1, qcnt++, 0));
}
}
vector<int> st;
for (int i = 1;i <= n;i++) st.push_back(i);
solve(st);
int act = 0;
for (int i = 0;i < k;i++) {
if (qtype[i]) cout << ans[i] << "\n", act++;
else cout << (ans[i] ? "yes" : "no") << "\n";
}
assert(act == tc);
}
/*
6 9
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
C 3
Q 5 1
C 6
Q 1 5
C 1
C 2
C 4
C 5
7 7
S 4 5
S 2 3
S 5 6
S 6 7
S 3 4
S 1 2
C 1
C 2
C 3
C 4
C 5
C 6
C 7
*/
Compilation message
servers.cpp: In function 'int main()':
servers.cpp:172:2: error: 'assert' was not declared in this scope
172 | assert(act == tc);
| ^~~~~~
servers.cpp:8:1: note: 'assert' is defined in header '<cassert>'; did you forget to '#include <cassert>'?
7 | #include <set>
+++ |+#include <cassert>
8 | //#include <ext/pb_ds/assoc_contatiner.hpp>
