#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, l, r) for (int i = (l); i < (r); ++i)
#define RVP(i, n) for (int i = (n - 1); i >= 0; --i)
#define ALL(x) (x).begin(), (x).end()
struct Query {
bool type;
int time;
int v;
};
struct Edge {
int to;
int time;
};
int main() {
int N, K;
cin >> N >> K;
vector<tuple<int, int, int>> Q(N + K - 1);
vector<vector<Edge>> Tree(N);
vector<int> ans(N + K - 1, -1);
REP(i, N + K - 1) {
auto &[c, a, b] = Q[i];
char s;
cin >> s >> a;
--a;
if (s == 'S') c = 0;
if (s == 'Q') c = 1;
if (s == 'C') c = 2;
if (c != 2) {
cin >> b;
--b;
}
if (c == 0) {
Tree[a].push_back({b, i});
Tree[b].push_back({a, i});
}
if (c == 1 and a == b) ans[i] = 1;
}
vector<vector<Query>> qv(N);
REP(i, N + K - 1) {
const auto &[c, a, b] = Q[i];
if (c == 0) continue;
if (c == 1) qv[a].push_back({false, i, b});
if (c == 2) qv[a].push_back({true, i, 0});
}
vector<bool> is_valid(N, true);
vector<int> subsize(N);
auto centroid_decompose = [&](auto &&self, const int root, auto &solve) -> void {
{
auto dfs = [&](auto &&self, const int v, const int p) -> int {
subsize[v] = 1;
for (const auto &[to, dust] : Tree[v]) {
if (not is_valid[to]) continue;
if (to == p) continue;
subsize[v] += self(self, to, v);
}
return subsize[v];
};
dfs(dfs, root, -1);
}
const int count_v = subsize[root];
int centroid = -1;
{
auto dfs = [&](auto &&self, const int v, const int p) -> void {
bool is_centroid = true;
for (const auto &[to, dust] : Tree[v]) {
if (not is_valid[to]) continue;
if (to == p) continue;
self(self, to, v);
if (subsize[to] > count_v / 2) is_centroid = false;
}
if (count_v - subsize[v] > count_v / 2) is_centroid = false;
if (is_centroid) centroid = v;
};
dfs(dfs, root, -1);
}
solve(centroid);
{
is_valid[centroid] = false;
vector<vector<int>> vertices;
for (const auto &[to, dust] : Tree[centroid]) {
if (not is_valid[to]) continue;
vertices.push_back({});
auto dfs = [&](auto &&self, const int v, const int p) -> void {
vertices.back().push_back(v);
is_valid[v] = false;
for (const auto &[to, dust2] : Tree[v]) {
if (not is_valid[to]) continue;
if (to == p) continue;
self(self, to, v);
}
};
dfs(dfs, to, centroid);
}
int cnt = 0;
for (const auto &ver : vertices) {
for (const int ve : ver) is_valid[ve] = true;
self(self, ver[0], solve);
for (const int ve : ver) is_valid[ve] = false;
++cnt;
}
}
};
vector<bool> is_inc(N), is_dec(N);
vector<int> froot(N), pa_time(N);
auto answer_query = [&](const int centroid) {
{
auto dfs = [&](auto &&self, const int v, const int p, const int last_time,
const int fr) -> void {
if (fr != -1) froot[v] = fr;
pa_time[v] = last_time;
for (const auto &[to, time] : Tree[v]) {
if (not is_valid[to]) continue;
if (to == p) continue;
if (is_inc[v] and (time == -1 or time > last_time)) is_inc[to] = true;
if (is_dec[v] and (time == -1 or time < last_time)) is_dec[to] = true;
self(self, to, v, time, fr == -1 ? to : fr);
}
};
is_inc[centroid] = is_dec[centroid] = true;
dfs(dfs, centroid, -1, -1, -1);
}
{
auto dfs = [&](auto &&self, const int v, const int p) -> void {
for (const auto &[type, id, b] : qv[v]) {
if (not type) {
if (not is_valid[b]) continue;
if (froot[v] == froot[b]) continue;
ans[id] = is_inc[v] and is_dec[b] and pa_time[v] <= id;
}
}
for (const auto &[to, dust] : Tree[v]) {
if (not is_valid[to]) continue;
if (to == p) continue;
self(self, to, v);
}
};
dfs(dfs, centroid, -1);
}
};
centroid_decompose(centroid_decompose, 0, answer_query);
REP(i, N + K - 1) {
if (ans[i] == -1) continue;
if (get<0>(Q[i]) == 1) {
cout << (ans[i] ? "yes" : "no") << '\n';
} else {
cout << ans[i] << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
5552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
5552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
5624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
5624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
5628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
5628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
5628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
5628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
5628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
5628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
80 ms |
5616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
80 ms |
5616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
