#include <bits/stdc++.h>
using namespace std;
#define lg long long
#define mid (lr+hr)/2
const lg N = 2e5+5;
vector<array<lg, 2>> adj[N];
lg anc[N][20], inc[N][20], mxm[N][20], depth[N], decr[N][20];
// lg head[N], in[N], out[N], tmp, sz[N], p[N], euler[N], co[N], loc[N], depth[N];
// struct Node{
// lg f;
// lg l;
// lg sz;
// lg mnm;
// bool inc;
// bool dec;
// Node()
// {
// sz = 1;
// f = l = 0;
// inc = dec = 0;
// mnm = 0;
// }
// } seg[N << 2];
// //cost, first, last, increase, decrease
// Node fake()
// {
// Node e;
// e.f = -1;
// return e;
// }
// Node merge(Node a, Node b)
// {
// if(a.f == -1) return b;
// if(b.f == -1) return a;
// Node c;
// c.f = a.f;
// c.l = b.l;
// c.sz = a.sz+b.sz;
// c.inc = (a.inc && b.inc && (a.l < b.f || a.l == -2 || b.f == -2));
// c.dec = (a.dec && b.dec && (a.l > b.f || a.l == -2 || b.f == -2));
// c.mnm = min(a.mnm, b.mnm);
// if(c.mnm == -2 && c.f != -2) c.inc = c.dec = 0;
// if(b.f == -2) c.inc = c.dec = 0;
// return c;
// }
// void build(lg node, lg lr, lg hr)
// {
// if(lr == hr)
// {
// seg[node].inc = seg[node].dec = 1;
// seg[node].l = seg[node].f = -2;
// seg[node].sz = 1;
// seg[node].mnm = seg[node].l;
// return;
// }
// build(node << 1, lr, mid);
// build(node << 1 | 1, mid+1, hr);
// seg[node] = merge(seg[node << 1], seg[node << 1 | 1]);
// return;
// }
// void update(lg node, lg lr, lg hr, lg idx, lg val)
// {
// if(lr > idx || hr < idx) return ;
// if(lr == hr)
// {
// seg[node].f = seg[node].l = val;
// seg[node].mnm = seg[node].l;
// return ;
// }
// update(node << 1, lr, mid, idx, val);
// update(node << 1 | 1, mid+1, hr, idx, val);
// seg[node] = merge(seg[node << 1], seg[node << 1 | 1]);
// return;
// }
// Node get(lg node, lg lr, lg hr, lg lq, lg hq)
// {
// if(lq > hr || lr > hq) return fake();
// if(lq <= lr && hr <= hq) return seg[node];
// return merge(get(node << 1, lr, mid, lq, hq), get(node << 1 | 1, mid+1, hr, lq, hq));
// }
// void dfs(lg src, lg par = -1)
// {
// sz[src] = 1;
// for(auto [it, c] : adj[src])
// {
// if(it == par) continue;
// depth[it] = depth[src]+1;
// p[it] = src;
// co[it] = c;
// dfs(it, src);
// sz[src] += sz[it];
// }
// return ;
// }
// void dfs2(lg src, lg par = -1)
// {
// in[src] = ++tmp;
// euler[tmp] = src;
// loc[src] = tmp;
// if(p[src] == adj[src][0][0]) reverse(adj[src].begin(), adj[src].end());
// for(auto &it : adj[src])
// {
// if(it[0] == par)
// {
// continue;
// }
// if(sz[it[0]] > sz[adj[src][0][0]]) swap(adj[src][0], it);
// }
// for(auto [it, c] : adj[src])
// {
// if(it == par)
// {
// continue;
// }
// head[it] = (it == adj[src][0][0] ? head[src] : it);
// dfs2(it, src);
// }
// out[src] = tmp;
// }
// lg lca(lg a, lg b)
// {
// while(head[a] != head[b])
// {
// if(depth[head[b]] > depth[head[a]]) swap(a, b);
// a = p[head[a]];
// }
// if(depth[b] > depth[a]) swap(a, b);
// return b;
// }
void dfs(lg src, lg par = -1)
{
for(auto [it, c] : adj[src])
{
if(it == par) continue;
anc[it][0] = src;
depth[it] = depth[src]+1;
mxm[it][0] = c;
inc[it][0] = (mxm[src][0] < c);
decr[it][0] = (mxm[src][0] > c);
for(int i = 1; i < 20; i++)
{
anc[it][i] = anc[anc[it][i-1]][i-1];
inc[it][i] = (inc[anc[it][i-1]][i-1] && inc[it][i-1]);
decr[it][i] = (decr[anc[it][i-1]][i-1] && decr[it][i-1]);
mxm[it][i] = max(mxm[anc[it][i-1]][i-1], mxm[it][i-1]);
}
dfs(it, src);
}
return;
}
lg lca(lg a, lg b)
{
if(depth[a] < depth[b]) swap(a, b);
lg diff = (depth[a]-depth[b]);
for(int i = 0; i < 20; i++)
{
if((1ll << i)&diff)
{
a = anc[a][i];
}
}
if(a == b) return a;
for(int i = 19; i >= 0; i--)
{
if(anc[a][i] == anc[b][i]) continue;
a = anc[a][i];
b = anc[b][i];
}
return anc[a][0];
}
int main()
{
#ifdef CYBER
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
lg n, k;
cin >> n >> k;
vector<array<lg, 3>> que;
lg id = 1;
k += n-1;
while(k--)
{
char c;
cin >> c;
if(c == 'S')
{
lg u, v;
cin >> u >> v;
que.push_back({c, u, v});
adj[u].push_back({v, id});
adj[v].push_back({u, id});
id++;
}
else if(c == 'Q')
{
lg u, v;
cin >> u >> v;
que.push_back({c, u, v});
}
else{
lg u;
cin >> u;
que.push_back({c, u, 0});
}
}
dfs(1);
lg ava = 0;
for(auto [c, a, b] : que)
{
if(c == 'S')
{
ava++;
}
else if(c == 'Q')
{
lg _lca = lca(a, b);
lg diff = depth[b]-depth[_lca];
lg d = a, e = b;
lg mx = 0, in = 1, de = 1;
for(int i = 0; i < 20 && diff > 0; i++)
{
if((1ll << i)&diff)
{
mx = max(mx, mxm[b][i]);
b = anc[b][i];
}
}
diff = depth[a]-depth[_lca];
for(int i = 0; i < 20 && diff > 0; i++)
{
if((1ll << i)&diff)
{
mx = max(mx, mxm[a][i]);
a = anc[a][i];
}
}
a = d, b = e;
diff = depth[b]-depth[_lca]-1;
for(int i = 0; i < 20 && diff > 0; i++)
{
if((1ll << i)&diff)
{
in &= inc[b][i];
b = anc[b][i];
}
}
diff = depth[a]-depth[_lca]-1;
for(int i = 0; i < 20 && diff > 0; i++)
{
if((1ll << i)&diff)
{
de &= decr[a][i];
a = anc[a][i];
}
}
// cout << a << ' ' << b << ' ' << _lca << '\n';
if(a != b) de &= (mxm[a][0] > mxm[b][0]);
// cout << de << ' ' << in << ' ' << mx << '\n';
cout << (de && in && mx <= ava ? "yes\n" : "no\n");
// swap(a, b);
// lg _lca = lca(a, b);
// lg cur = 1;
// lg la = 1e18;
// Node o;
// while(head[b] != head[_lca] && cur)
// {
// o = get(1, 1, n, loc[head[b]], loc[b]);
// // cout << b << ' ';
// cur &= (o.l < la);
// la = o.f;
// cur &= o.inc;
// cur &= (o.mnm > -2);
// // cout << "MNM: " << o.mnm << '\n';
// b = p[head[b]];
// }
// // cout << b << ' ' << _lca << '\n';
// // cout << "DEC " << cur << ' ';
// o = get(1, 1, n, loc[_lca], loc[b]);
// cur &= o.inc;
// // cout << "DEC " << cur << ' ';
// if(_lca != b) cur &= (o.l < la);
// // cout << "DEC " << cur << ' ';
// la = -1e18;
// while(head[a] != head[_lca] && cur)
// {
// o = get(1, 1, n, loc[head[a]], loc[a]);
// // cout << a << ' ';
// cur &= (o.l > la);
// la = o.f;
// cur &= o.dec;
// cur &= (o.mnm > -2);
// // cout << "MNM: " << o.mnm << '\n';
// a = p[head[a]];
// }
// // cout << a << ' ' << _lca << '\n';
// o = get(1, 1, n, loc[_lca], loc[a]);
// // cout << "DEC " << cur << ' ';
// cur &= o.dec;
// // cout << "DEC " << cur << ' ';
// if(_lca != a) cur &= (o.l > la);
// // cout << "DEC " << cur << ' ';
// cout << (cur ? "yes\n" : "no\n");
}
// for(int i = 1; i <= n; i++)
// {
// lg x = get(1, 1, n, i, i).f;
// if(x > 1e15) cout << "inf ";
// else cout << x << ' ';
// }
// cout << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
13836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
13836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
14004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
14004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
14008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
14008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
13784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
13784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
13864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
13864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
13868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
13868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
