#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <string>
#include <sstream>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <stack>
#include <cstdio>
#include <climits>
#include <tuple>
#include <ctime>
#include <cstring>
#include <numeric>
#include <functional>
#include <chrono>
#include <cassert>
#include <bitset>
#include <fstream>
#define sz(a) ((int)((a).size()))
// printf("%.10f\n", ans);
using ll = long long;
using namespace std;
const ll mod = 1e9 + 7;
const int N = 2e5 + 1, inf = 1e9;
struct Query {
char t;
int u, v;
};
int n, q, timer;
vector<int> par, cap, tin, tout, head, arr, binc, bdec, depth;
vector<Query> qu;
vector<vector<int>> tree, up;
void dfs(int u, int p)
{
par[u] = p;
int id = -1;
cap[u] = 1;
for (int i = 0; i < sz(tree[u]); i++)
{
int v = tree[u][i];
if (v == p) id = i;
else
{
dfs(v, u);
cap[u] += cap[v];
}
}
if (id != -1)
{
swap(tree[u][id], tree[u].back());
tree[u].pop_back();
}
for (int i = 1; i < sz(tree[u]); i++)
{
int v = tree[u][i];
if (cap[v] > cap[tree[u][0]]) swap(tree[u][i], tree[u][0]);
}
}
void hld(int u, int h)
{
tin[u] = timer++;
if (u != 0) depth[u] = depth[par[u]] + 1;
head[u] = h;
up[u][0] = par[u];
for (int i = 1; i < 20; i++) up[u][i] = up[up[u][i - 1]][i - 1];
for (int i = 0; i < sz(tree[u]); i++)
{
int v = tree[u][i];
if (i == 0) hld(v, h);
else hld(v, v);
}
tout[u] = timer;
}
bool ok(int u, int v)
{
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int find_lca(int u, int v)
{
if (ok(u, v)) return u;
if (ok(v, u)) return v;
for (int i = 19; i >= 0; i--) if (!ok(up[u][i], v)) u = up[u][i];
return up[u][0];
}
int go_up(int u, int k)
{
for (int i = 19; i >= 0; i--)
{
if ((1 << i) <= k)
{
k -= (1 << i);
u = up[u][i];
}
}
return u;
}
bool ok_inc(int l, int r)
{
return l >= binc[r];
}
bool is_inc(int u, int v)
{
while (depth[u] >= depth[v])
{
int h = head[u];
if (depth[h] < depth[v]) h = v;
int l = tin[h], r = tin[u];
if (!ok_inc(l, r)) return 0;
if (h == v) break;
if (arr[tin[par[h]]] < arr[tin[h]]) return 0;
u = par[h];
}
return 1;
}
bool ok_dec(int l, int r)
{
return l >= bdec[r];
}
bool is_dec(int u, int v)
{
while (depth[u] >= depth[v])
{
int h = head[u];
if (depth[h] < depth[v]) h = v;
int l = tin[h], r = tin[u];
if (!ok_dec(l, r)) return 0;
if (h == v) break;
if (arr[tin[par[h]]] > arr[tin[h]]) return 0;
u = par[h];
}
return 1;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q;
par = cap = tin = tout = head = arr = binc = bdec = depth = vector<int>(n);
qu = vector<Query>(n + q - 1);
tree = vector<vector<int>>(n);
up = vector<vector<int>>(n, vector<int>(20));
for (int i = 0; i < n + q - 1; i++)
{
cin >> qu[i].t >> qu[i].u >> qu[i].v;
qu[i].u--, qu[i].v--;
if (qu[i].t == 'S')
{
tree[qu[i].u].push_back(qu[i].v);
tree[qu[i].v].push_back(qu[i].u);
}
}
dfs(0, 0);
hld(0, 0);
for (int i = 0; i < n + q - 1; i++)
{
if (qu[i].t == 'S')
{
if (par[qu[i].u] == qu[i].v) swap(qu[i].u, qu[i].v);
arr[tin[qu[i].v]] = i;
}
}
binc[0] = 0;
bdec[0] = 0;
for (int i = 1; i < n; i++)
{
if (arr[i] < arr[i - 1]) binc[i] = i;
else binc[i] = binc[i - 1];
if (arr[i] > arr[i - 1]) bdec[i] = i;
else bdec[i] = bdec[i - 1];
}
for (int i = 0; i < n + q - 1; i++)
{
if (qu[i].t == 'Q')
{
int u = qu[i].u, v = qu[i].v;
if (u == v)
{
cout << "yes\n";
continue;
}
int lca = find_lca(u, v);
if (u == lca)
{
int dist = depth[v] - depth[u];
int k = go_up(v, dist - 1);
if (arr[tin[k]] < i && is_inc(v, k)) cout << "yes\n";
else cout << "no\n";
}
else if (v == lca)
{
int dist = depth[u] - depth[v];
int k = go_up(u, dist - 1);
if (arr[tin[u]] < i && is_dec(u, k)) cout << "yes\n";
else cout << "no\n";
}
else
{
int dist = depth[v] - depth[lca];
int v1 = go_up(v, dist - 1);
dist = depth[u] - depth[lca];
int u1 = go_up(u, dist - 1);
if (arr[tin[u]] < i && arr[tin[u1]] > arr[tin[v1]] && is_inc(v, v1) && is_dec(u, u1)) cout << "yes\n";
else cout << "no\n";
}
}
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
28 ms |
2892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
28 ms |
2892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
28 ms |
3016 KB |
Output is correct |
| 2 |
Correct |
158 ms |
31744 KB |
Output is correct |
| 3 |
Correct |
156 ms |
31760 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
28 ms |
3016 KB |
Output is correct |
| 2 |
Correct |
158 ms |
31744 KB |
Output is correct |
| 3 |
Correct |
156 ms |
31760 KB |
Output is correct |
| 4 |
Execution timed out |
3557 ms |
1748 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
24 ms |
2888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
24 ms |
2888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
29 ms |
2888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
29 ms |
2888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
31 ms |
2880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
31 ms |
2880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
36 ms |
2932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
36 ms |
2932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
