#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef int64_t ll;
#define SZ(x) (int) x.size()
const int N = 120'005, LOG = 18, B = 700;
vector<array<int, 3>> adj[N];
vector<int> dp[N];
int lst;
int solve(int i, int par) {
if (~dp[i][par]) return dp[i][par];
int j = (par == SZ(adj[i])? 0 : par + 1);
dp[i][par] = 1;
if (j < SZ(adj[i])) {
if (adj[i][j][1] > lst) return dp[i][par];
dp[i][par] += solve(adj[i][j][0], adj[i][j][2]) + solve(i, j) - 1;
}
return dp[i][par];
}
int st[N], en[N], sz[N], curt;
array<int, 2> par[N];
bool isanc(int u, int v) {
return st[u] <= st[v] && en[v] <= en[u];
}
struct sparse {
array<int, 2> a[2 * N][LOG + 1];
int n;
int logs[2 * N];
void build(int _n) {
n = _n;
logs[1] = 0;
for (int j = 2; j <= n; j++) {
logs[j] = logs[j >> 1] + 1;
}
for (int j = 1; j <= LOG; j++) {
for (int i = 0; i + (1 << (j - 1)) < n; i++) {
a[i][j] = min(a[i][j - 1], a[i + (1 << (j - 1))][j - 1]);
}
}
}
int query(int u, int v) {
if (st[u] > st[v]) swap(u, v);
if (isanc(u, v)) {
return u;
}
int l = en[u], r = st[v];
int lg = logs[r - l + 1];
array<int, 2> mn = min(a[l][lg], a[r - (1 << lg) + 1][lg]);
return mn[1];
}
} lca;
void dfs(int i, int h, int p, int part) {
lca.a[curt][0] = {h, i};
st[i] = curt++;
sz[i] = 1;
par[i] = {p, part};
for (int j = 0; j < SZ(adj[i]); j++) {
auto [nxt, t, nxtidx] = adj[i][j];
if (nxt == p) {
swap(adj[i][j], adj[i][SZ(adj[i]) - 1]);
if (j != SZ(adj[i]) - 1) j--;
continue;
}
dfs(nxt, h + 1, i, t);
sz[i] += sz[nxt];
if (sz[nxt] > sz[adj[i][0][0]]) swap(adj[i][0], adj[i][j]);
lca.a[curt][0] = {h, i};
curt++;
}
en[i] = curt - 1;
}
vector<array<int, 4>> ask[N];
int ans[N];
void process(int i, int p) {
for (auto [a, b, t, idx] : ask[i]) {
int cur = a, lst1 = -1e9;
bool ok = 1;
while (cur != i) {
ok &= lst1 < par[cur][1];
lst1 = par[cur][1];
cur = par[cur][0];
}
cur = b;
int lst2 = 1e9;
while (cur != i) {
ok &= par[cur][1] < lst2;
lst2 = par[cur][1];
cur = par[cur][0];
}
ok &= lst1 < lst2;
if (b != i) {
ok &= par[b][1] <= t;
} else if (a != i) {
ok &= lst1 <= t;
}
ans[idx] += ok;
}
for (auto [nxt, t, nxtidx] : adj[i]) {
if (nxt == p) continue;
process(nxt, i);
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n, q;
cin >> n >> q;
q += n - 1;
pair<char, vector<int>> v[q];
for (int i = 0; i < q; i++) {
cin >> v[i].first;
if (v[i].first == 'S') {
int a, b;
cin >> a >> b;
int x = adj[b].size(), y = adj[a].size();
adj[a].push_back({b, i, x});
adj[b].push_back({a, i, y});
v[i].second = {a, b};
} else if (v[i].first == 'Q') {
int a, b;
cin >> a >> b;
v[i].second = {a, b};
} else {
int a;
cin >> a;
v[i].second = {a};
}
}
dfs(1, 0, 1, 0);
lca.build(curt);
for (int i = 1; i <= n; i++) {
dp[i].resize(adj[i].size() + 1);
for (int j = 0; j <= SZ(adj[i]); j++) {
dp[i][j] = -1;
}
}
vector<array<int, 3>> upd;
lst = -1;
for (int i = 0; i < q; i++) {
if (upd.size() == B) {
lst = i - 1;
upd.clear();
for (int j = 1; j <= n; j++) {
for (int k = 0; k <= SZ(adj[j]); k++) {
dp[j][k] = -1;
}
}
}
if (v[i].first == 'S') {
int a = v[i].second[0], b = v[i].second[1];
if (isanc(b, a)) swap(a, b);
upd.push_back({a, b, i});
} else if (v[i].first == 'Q') {
int a = v[i].second[0], b = v[i].second[1];
int mid = lca.query(a, b);
ask[mid].push_back({b, a, i, i});
} else {
int x = v[i].second[0];
ans[i] += solve(x, adj[x].size());
for (auto [a, b, t] : upd) {
if (isanc(b, x)) {
ask[b].push_back({x, b, t - 1, i});
} else if (isanc(a, x)) {
ask[a].push_back({x, a, t - 1, i});
} else {
int mid = lca.query(a, x);
ask[mid].push_back({x, a, t - 1, i});
}
}
}
}
process(1, 1);
for (int i = 0; i < q; i++) {
if (v[i].first == 'Q') {
cout << (ans[i]? "yes\n" : "no\n");
} else if (v[i].first == 'C') {
cout << ans[i] << '\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
24524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
24524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
47004 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
47004 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
24756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
24756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
24268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
24268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
24704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
24704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
24724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
24724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
