#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define x first
#define y second
ll N, K;
vector<pair<ll, ll>> T[120005];
ll S[120005], vis[120005], Ans[120005];
struct Query{
ll v, t, n;
bool operator< (const Query &r) const{
return t < r.t;
}
};
vector<Query> Qry[120005];
struct Fen{
ll T[120005];
void upd(ll k, ll v) { while(k <= N) T[k] += v, k += k & -k; }
ll qry(ll k) { ll r = 0; while(k >= 1) r += T[k], k -= k & -k; return r; }
}seg;
ll Size(ll u, ll p){
S[u] = 1;
for(auto e : T[u]){
if(e.x != p && !vis[e.x]) S[u] += Size(e.x, u);
}
return S[u];
}
ll Cent(ll u, ll p, ll n){
for(auto e : T[u]){
if(e.x != p && !vis[e.x] && S[e.x] > n / 2) return Cent(e.x, u, n);
}
return u;
}
ll Num[120005], X[120005], Y[120005], Z[120005];
void dfs(ll u, ll p, ll pc, vector<ll> &V, ll n){
V.push_back(u); Num[u] = n;
for(auto e : T[u]){
if(e.x == p || vis[e.x]) continue;
X[e.x] = -1, Y[e.x] = -1, Z[e.x] = min(Z[u], e.y);
if(X[u] != -1 && pc > e.y) X[e.x] = X[u];
if(Y[u] != -1 && pc < e.y) Y[e.x] = e.y;
dfs(e.x, u, e.y, V, n);
}
}
void dnc(ll _u){
ll c = Cent(_u, -1, Size(_u, -1));
vis[c] = 1;
vector<vector<ll>> Sub;
Sub.push_back({c});
X[c] = 1, Y[c] = 0, Z[c] = N, Num[c] = c;
for(auto e : T[c]){
if(vis[e.x]) continue;
X[e.x] = Y[e.x] = Z[e.x] = e.y;
Sub.push_back({});
dfs(e.x, -1, e.y, Sub.back(), e.x);
}
vector<Query> Q;
vector<pair<ll, ll>> V, His;
for(ll i = 0; i < Sub.size(); i++){
for(auto u : Sub[i]){
if(Y[u] != -1) V.push_back({Y[u], Z[u]});
for(auto q : Qry[u]){
if(q.v == -1){
Q.push_back({u, q.t, q.n});
} else if(Num[q.v] != 0 && Num[u] != Num[q.v] && Y[u] != -1 && Y[u] <= q.t && X[q.v] != -1 && Z[u] >= X[q.v]){
Ans[q.n] = -99;
}
}
}
}
sort(Q.begin(), Q.end()); sort(V.begin(), V.end());
for(ll i = 0, j = 0; i < Q.size(); i++){
while(j < V.size() && V[j].x <= Q[i].t){
seg.upd(V[j].y, 1); His.push_back({V[j].y, 1});
j++;
}
if(X[Q[i].v] != -1) Ans[Q[i].n] += seg.qry(N) - seg.qry(X[Q[i].v] - 1);
}
for(auto t : His) seg.upd(t.x, -t.y);
for(ll k = 0; k < Sub.size(); k++){
Q.clear(); V.clear(); His.clear();
for(auto u : Sub[k]){
if(Y[u] != -1) V.push_back({Y[u], Z[u]});
for(auto q : Qry[u]){
if(q.v == -1) Q.push_back({u, q.t, q.n});
}
Num[u] = 0;
}
sort(Q.begin(), Q.end()); sort(V.begin(), V.end());
for(ll i = 0, j = 0; i < Q.size(); i++){
while(j < V.size() && V[j].x <= Q[i].t){
seg.upd(V[j].y, 1); His.push_back({V[j].y, 1});
j++;
}
if(X[Q[i].v] != -1) Ans[Q[i].n] -= seg.qry(N) - seg.qry(X[Q[i].v] - 1);
}
for(auto t : His) seg.upd(t.x, -t.y);
}
for(auto e : T[c]){
if(vis[e.x]) continue;
dnc(e.x);
}
}
int main(){
cin.tie(0) -> sync_with_stdio(0);
cin >> N >> K;
ll t = 0;
for(ll i = 1; i <= N + K - 1; i++){
char op; ll u, v; cin >> op >> u;
if(op == 'S'){
cin >> v; t++;
T[u].push_back({v, t});
T[v].push_back({u, t});
} else if(op == 'Q'){
cin >> v;
if(u == v){
Ans[i - t] = -99; continue;
}
Qry[u].push_back({v, t, i - t});
Ans[i - t] = -100;
} else {
Qry[u].push_back({-1, t, i - t});
}
}
dnc(1);
for(ll i = 1; i <= K; i++){
if(Ans[i] < 0){
cout << (Ans[i] == -100 ? "no\n" : "yes\n");
} else {
cout << Ans[i] + 1 << '\n';
}
}
}
Compilation message
servers.cpp: In function 'void dnc(ll)':
servers.cpp:65:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(ll i = 0; i < Sub.size(); i++){
| ~~^~~~~~~~~~~~
servers.cpp:79:28: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(ll i = 0, j = 0; i < Q.size(); i++){
| ~~^~~~~~~~~~
servers.cpp:80:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | while(j < V.size() && V[j].x <= Q[i].t){
| ~~^~~~~~~~~~
servers.cpp:88:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(ll k = 0; k < Sub.size(); k++){
| ~~^~~~~~~~~~~~
servers.cpp:99:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(ll i = 0, j = 0; i < Q.size(); i++){
| ~~^~~~~~~~~~
servers.cpp:100:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | while(j < V.size() && V[j].x <= Q[i].t){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
18840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
18840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
18840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
18840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
16752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
16752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
14772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
14772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
14740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
14740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
14744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
14744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
