#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 = 300, inf = 1e9;
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], curt, eulerst[N], euleren[N], eulert;
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++;
eulerst[i] = eulert++;
par[i] = {p, part};
for (int j = 0; j < SZ(adj[i]); j++) {
auto [nxt, t, nxtidx] = adj[i][j];
if (nxt == p) continue;
dfs(nxt, h + 1, i, t);
lca.a[curt][0] = {h, i};
curt++;
}
en[i] = curt - 1;
euleren[i] = eulert - 1;
}
vector<array<int, 2>> ask[N];
int ans[2 * N];
struct sqrt_decomp {
const int b = 350;
int a[N], lazy[350];
int n;
void init(int _n, int _v) {
n = _n;
for (int i = 0; i < n; i++) {
a[i] = _v;
}
for (int i = 0; i <= n / b; i++) {
lazy[i] = -1;
}
}
void set(int l, int r, int v) {
int s = l / b, e = r / b;
if (s == e) {
for (int i = l; i <= r; i++) {
a[i] = v;
}
return;
}
for (int i = s + 1; i <= e - 1; i++) {
lazy[i] = v;
}
int x = s * b, y = (s + 1) * b - 1;
if (lazy[s] != -1) {
for (int i = x; i <= y; i++) {
a[i] = lazy[s];
}
lazy[s] = -1;
}
for (int i = l; i <= y; i++) {
a[i] = v;
}
x = e * b, y = (e + 1) * b - 1;
if (lazy[e] != -1) {
for (int i = x; i <= y; i++) {
a[i] = lazy[e];
}
lazy[e] = -1;
}
for (int i = x; i <= r; i++) {
a[i] = v;
}
}
int get(int i) {
int x = i / b;
if (lazy[x] != -1) {
return lazy[x];
}
return a[i];
}
} Inc, Dec;
set<int> activeinc, activedec;
bool ininc[N], indec[N];
pair<char, vector<int>> v[N];
void process(int i, int p) {
for (auto [nxt, t, nxtidx] : adj[i]) {
if (nxt == p) continue;
process(nxt, i);
}
ininc[eulerst[i]] = 1;
indec[eulerst[i]] = 1;
for (auto [idx, t] : ask[i]) {
int a, b;
if (v[idx].first == 'Q') {
a = v[idx].second[1], b = v[idx].second[0];
} else {
a = v[t].second[0], b = v[t].second[1];
int x = v[idx].second[0];
if (isanc(b, x)) {
a = x;
} else {
b = a;
a = x;
}
}
if (!indec[eulerst[a]] || !ininc[eulerst[b]]) continue;
int lst1 = Dec.get(eulerst[a]), lst2 = Inc.get(eulerst[b]);
bool ok = lst1 < lst2;
int mx;
if (v[idx].first == 'Q') {
mx = idx;
} else {
mx = t - 1;
}
if (b != i) {
ok &= par[b][1] <= mx;
} else if (a != i) {
ok &= lst1 <= mx;
}
ans[idx] += ok;
}
// for (auto [a, b, t, idx] : ask[i]) {
// if (!indec[eulerst[a]] || !ininc[eulerst[b]]) continue;
// int lst1 = Dec.get(eulerst[a]), lst2 = Inc.get(eulerst[b]);
// bool ok = lst1 < lst2;
// if (b != i) {
// ok &= par[b][1] <= t;
// } else if (a != i) {
// ok &= lst1 <= t;
// }
// ans[idx] += ok;
// }
ask[i].clear();
if (i == 1) return;
int part = par[i][1];
for (auto [nxt, t, nxtidx] : adj[i]) {
if (nxt == p) continue;
if (part < t) {
Inc.set(eulerst[nxt], euleren[nxt], part);
auto it = activedec.lower_bound(eulerst[nxt]);
while (it != activedec.end() && *it <= euleren[nxt]) {
indec[*it] = 0;
it = activedec.erase(it);
}
Dec.set(eulerst[nxt], euleren[nxt], inf);
} else {
auto it = activeinc.lower_bound(eulerst[nxt]);
while (it != activeinc.end() && *it <= euleren[nxt]) {
ininc[*it] = 0;
it = activeinc.erase(it);
}
Inc.set(eulerst[nxt], euleren[nxt], -inf);
Dec.set(eulerst[nxt], euleren[nxt], part);
}
}
activeinc.insert(eulerst[i]);
Inc.set(eulerst[i], eulerst[i], part);
activedec.insert(eulerst[i]);
Dec.set(eulerst[i], eulerst[i], part);
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n, q;
cin >> n >> q;
q += n - 1;
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});
ask[mid].push_back({i, -1});
} 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 {
// int mid = lca.query(a, x);
// ask[mid].push_back({x, a, t - 1, i});
// }
// }
for (auto [a, b, t] : upd) {
if (isanc(b, x)) {
ask[b].push_back({i, t});
} else {
int mid = lca.query(a, x);
ask[mid].push_back({i, t});
}
}
// for (auto [a, b, t, idx] : ask[i]) {
// if (!indec[eulerst[a]] || !ininc[eulerst[b]]) continue;
// int lst1 = Dec.get(eulerst[a]), lst2 = Inc.get(eulerst[b]);
// bool ok = lst1 < lst2;
// if (b != i) {
// ok &= par[b][1] <= t;
// } else if (a != i) {
// ok &= lst1 <= t;
// }
// ans[idx] += ok;
// }
}
}
Dec.init(eulert, -inf);
Inc.init(eulert, inf);
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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
45 ms |
49256 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
45 ms |
49256 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
43 ms |
48680 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
43 ms |
48680 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
44 ms |
49312 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
44 ms |
49312 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
47 ms |
48692 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
47 ms |
48692 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
50 ms |
49232 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
50 ms |
49232 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
46 ms |
49224 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
46 ms |
49224 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
