//khodaya khodet komak kon
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <pii, int> ppi;
typedef pair <int, pii> pip;
typedef pair <pii, pii> ppp;
typedef pair <ll, ll> pll;
# define A first
# define B second
# define endl '\n'
# define sep ' '
# define all(x) x.begin(), x.end()
# define kill(x) return cout << x << endl, 0
# define SZ(x) int(x.size())
# define lc id << 1
# define rc id << 1 | 1
# define fast_io ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
const int xn = 3e5 + 10;
const int xm = - 20 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 1e9 + 7;//998244353;
const int base = 257;
int n, k, sz[xn], ans[xn], fen[xn], a[xn], qt[xn];
vector <int> QG[xn], vec, V;
vector <pii> adj[xn], Q[xn];
bool hide[xn], mark[xn], fl[2][xn];
void plant(int v, int p = - 1){
sz[v] = 1;
for (pii u : adj[v])
if (!hide[u.A] && u.A != p)
plant(u.A, v), sz[v] += sz[u.A];
}
int find_centroid(int v, int s, int p = - 1){
for (pii u : adj[v])
if (!hide[u.A] && u.A != p && s < sz[u.A] * 2)
return find_centroid(u.A, s, v);
return v;
}
bool cmp(pii x, pii y){
return y.B < x.B;
}
void DFS(int v, int p = - 1){
fl[0][v] = fl[0][p];
if (!hide[p])
fl[0][v] &= (a[v] < a[p]);
fl[1][v] = fl[1][p];
if (!hide[p])
fl[1][v] &= (a[p] < a[v]);
vec.push_back(v);
for (pii u : adj[v])
if (!hide[u.A] && u.A != p)
a[u.A] = u.B, DFS(u.A, v);
}
void mofen(int pos, int val){
for (pos += 5; pos < xn; pos += pos & - pos)
fen[pos] += val;
}
int gefen(int pos){
int res = 0;
for (pos += 5; 0 < pos; pos -= pos & - pos)
res += fen[pos];
return res;
}
void solve(int v){
plant(v);
v = find_centroid(v, sz[v]);
hide[v] = true;
sort(all(adj[v]), cmp);
a[v] = 0, mofen(0, 1);
mark[v] = true, V.clear();
V.push_back(v);
fl[0][v] = fl[1][v] = true;
for (pii u : adj[v]){
if (hide[u.A])
continue;
vec.clear();
a[u.A] = u.B, DFS(u.A, v);
for (int x : vec){
V.push_back(x);
for (pii y : Q[x])
if (mark[y.A])
ans[y.B] = (fl[1][y.A] && fl[0][x] && a[y.A] <= y.B);
for (int y : QG[x])
if (fl[0][x])
ans[y] += gefen(y);
}
for (int x : vec)
if (fl[1][x])
mofen(a[x], 1), mark[x] = true;
}
for (pii y : Q[v])
if (mark[y.A])
ans[y.B] = (fl[1][y.A] && a[y.A] <= y.B);
for (int y : QG[v])
ans[y] += gefen(y);
for (int x : V)
if (fl[1][x])
mofen(a[x], - 1), mark[x] = false;
for (pii u : adj[v])
if (!hide[u.A])
solve(u.A);
}
int main(){
fast_io;
cin >> n >> k;
for (int i = 1; i < n + k; ++ i){
char c;
int x, y;
cin >> c;
if (c == 'S'){
cin >> x >> y;
adj[x].push_back({y, i});
adj[y].push_back({x, i});
}
else if (c == 'Q'){
cin >> x >> y;
Q[y].push_back({x, i});
qt[i] = 1;
}
else{
cin >> x;
QG[x].push_back(i);
qt[i] = 2;
}
}
solve(1);
for (int i = 1; i < n + k; ++ i){
if (qt[i] == 2)
cout << ans[i] << endl;
else if (qt[i] == 1){
if (ans[i])
cout << "yes\n";
else
cout << "no\n";
}
}
return 0;
}
/*
6 13
C 1
S 1 2
C 1
S 1 3
C 1
S 3 4
C 1
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5
C 1
C 2
C 3
C 4
C 5
C 6
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
24636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
24636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
24644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
24644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
24644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
24644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
24644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
24644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
24600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
24600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
24592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
24592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
