#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 2e5 + 5;
const int oo = 2e9;
struct IT {
int st[N << 2], lz[N << 2];
void dolz(int i,int l,int r){
if(!lz[i]) return;
int x = lz[i], mid = (l + r) / 2; lz[i] = 0;
st[i << 1] += x * (mid - l + 1), st[i << 1|1] += x * (r - mid);
lz[i << 1] += x, lz[i << 1|1] += x;
}
void update(int i,int l,int r,int u,int v,int x){
if(l > r || r < u || v < l) return;
if(u <= l && r <= v){
st[i] += x * (r - l + 1);
lz[i] += x;
return;
}
dolz(i, l, r);
int mid = (l + r) / 2;
update(i << 1, l, mid, u, v, x);
update(i << 1|1, mid + 1, r, u, v, x);
}
int get(int i,int l,int r,int u,int v){
if(l > r || r < u || v < l) return 0;
if(u <= l && r <= v) return st[i];
dolz(i, l, r);
int mid = (l + r) / 2;
return get(i << 1, l, mid, u, v) + get(i << 1|1, mid + 1, r, u, v);
}
} f[2];
struct DSU{
int par[N];
void re(int n){
for(int i = 1; i <= n; i ++) par[i] = i;
}
int fin(int u){
return par[u] == u ? u : par[u] = fin(par[u]);
}
void dsu(int u,int v){
u = fin(u);
v = fin(v);
if(u == v) return;
par[u] = v;
}
} g[2];
int n, q, T[N], X[N], Y[N], in[N], demin, en[N], head[N], pa[N], dp[N][22], d[N], be[N], h[N], key[2][N], tn[N];
vector<pii> p[N];
bool kt(int u,int v){
return in[u] <= in[v] && in[v] <= en[u];
}
int LCA(int u,int v){
if(kt(u, v)) return u;
int lca = u;
for(int i = 20; i >= 0; i --) if(kt(dp[u][i], v)) lca = dp[u][i]; else u = dp[u][i];
return lca;
}
void dfs(int u,int v){
d[u] = 1;
for(auto [j, w] : p[u]) if(j != v){
dfs(j, u);
d[u] += d[j];
pa[j] = u;
h[j] = w;
}
}
int scc = 1;
vector<int> vr[N], b[N];
void hld(int u,int v){
in[u] = ++demin;
if(!head[scc]) head[scc] = u;
be[u] = scc;
tn[demin] = u;
if(!v){
for(int i = 0; i <= 20; i ++) dp[u][i] = u;
}else{
dp[u][0] = v;
for(int i = 1; i <= 20; i ++) dp[u][i] = dp[dp[u][i - 1]][i - 1];
}
int mx = 0, val = 0;
for(auto [j, w] : p[u]) if(j != v && d[j] > d[mx]) val = w, mx = j;
key[0][u] = mx, key[1][u] = val;
if(mx) hld(mx, u);
for(auto [j, w] : p[u]) if(j != v && j != mx){
scc++;
vr[u].pb(w);
hld(j, u);
}
sort(all(vr[u]));
for(auto j : vr[u]) b[u].pb(0);
en[u] = demin;
}
void up(int u,int tmp){
if(h[pa[u]] <= tmp){
if(pa[u] == 1){
g[0].dsu(u, pa[u]);
g[1].dsu(u, pa[u]);
}else{
if(h[pa[u]] > h[u]) g[0].dsu(u, pa[u]);
else g[1].dsu(u, pa[u]);
}
for(auto [j, w] : p[u]) if(j != pa[u]){
if(w > h[u] && w <= tmp) g[1].dsu(j, u);
if(w < h[u] && w <= tmp) g[0].dsu(j, u);
}
}
int v = pa[g[1].fin(u)], val = f[0].get(1, 1, n, in[u], in[u]);
if(key[0][pa[u]] != u){
int dr = lower_bound(all(vr[pa[u]]), h[u]) - vr[pa[u]].begin();
b[pa[u]][dr] += val; // add
if(key[1][pa[u]] < h[u]) f[1].update(1, 1, n, in[pa[u]], in[pa[u]], val);
}
u = pa[u];
while(true){
if(be[u] == be[v]){
f[0].update(1, 1, n, in[v], in[u], val);
return;
}
int j = pa[head[be[u]]];
if(h[head[be[u]]] > key[1][tn[in[j]]]) f[1].update(1, 1, n, in[j], in[j], val);
int dr = lower_bound(all(vr[j]), h[head[be[u]]]) - vr[j].begin();
b[j][dr] += val; // add
f[0].update(1, 1, n, in[head[be[u]]], in[u], val);
u = j;
}
}
int query(int u,int v){
int lca = LCA(u, v);
int fu = g[0].fin(u), fv = g[1].fin(v);
if(kt(fu, lca) && kt(fv, lca)) return 1;
return 0;
}
int solve(int u){
int ans = f[0].get(1, 1, n, in[u], in[u]);
if(u == 1) return ans;
int v = pa[g[0].fin(u)];
// cerr << v << " " << ans << " f\n";
if(key[0][pa[u]] != u){
int dr = upper_bound(all(vr[pa[u]]), h[u]) - vr[pa[u]].begin();
for(int i = dr; i < vr[pa[u]].size(); i ++) ans += b[pa[u]][i];
// cerr << ans << " d\n";
ans++;
if(key[1][pa[u]] > h[u]) ans += f[0].get(1, 1, n, in[key[0][pa[u]]], in[key[0][pa[u]]]);
cerr << f[0].get(1, 1, n, in[key[0][pa[u]]], in[key[0][pa[u]]]) << "t\n";
}else{
ans += f[1].get(1, 1, n, in[pa[u]], in[pa[u]]);
// cerr << f[1].get(1, 1, n, in[pa[u]], in[pa[u]]) << " g\n";
}
u = pa[u];
while(true){
if(be[u] == be[v]){
if(u == v) return ans;
ans += f[1].get(1, 1, n, in[v], in[u] - 1);
return ans;
}
int j = pa[head[be[u]]];
// cerr << j << " t\n";
int k = head[be[u]];
int pos = upper_bound(all(vr[j]), h[k]) - vr[j].begin();
for(int i = pos; i < vr[j].size(); i ++) ans += b[j][i];
ans += f[1].get(1, 1, n, in[k], in[u] - 1);
ans++;
if(key[1][j] > h[k]) ans += f[0].get(1, 1, n, in[key[0][j]], in[key[0][j]]);
u = j;
}
return ans;
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "v"
if(fopen(task ".inp","r")){
freopen(task ".inp","r",stdin);
freopen(task ".out","w",stdout);
}
cin >> n >> q;
q = n + q - 1;
g[1].re(n), g[0].re(n);
for(int i = 1; i <= q; i ++){
char c; cin >> c;
if(c == 'S'){
cin >> X[i] >> Y[i];
T[i] = 0,
p[X[i]].pb({Y[i], i});
p[Y[i]].pb({X[i], i});
}else if(c == 'Q'){
T[i] = 1;
cin >> X[i] >> Y[i];
}else{
T[i] = 2;
cin >> X[i];
}
}
pa[1] = 1;
h[1] = 0;
dfs(1, 0);
hld(1, 0);
for(int i = 1; i <= n; i ++) f[0].update(1, 1, n, in[i], in[i], 1), f[1].update(1, 1, n, in[i], in[i], 1);
for(int i = 1; i <= q; i ++){
if(T[i] == 0){
if(in[X[i]] < in[Y[i]]) swap(X[i], Y[i]);
up(X[i], i);
}else if(T[i] == 1){
cout << (query(Y[i], X[i]) == 1 ? "yes\n" : "no\n");
}else {
cout << solve(X[i]) << "\n";
}
}
}
Compilation message
servers.cpp: In function 'void hld(int, int)':
servers.cpp:120:12: warning: unused variable 'j' [-Wunused-variable]
120 | for(auto j : vr[u]) b[u].pb(0);
| ^
servers.cpp: In function 'int solve(int)':
servers.cpp:177:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
177 | for(int i = dr; i < vr[pa[u]].size(); i ++) ans += b[pa[u]][i];
| ~~^~~~~~~~~~~~~~~~~~
servers.cpp:198:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
198 | for(int i = pos; i < vr[j].size(); i ++) ans += b[j][i];
| ~~^~~~~~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:211:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
211 | freopen(task ".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:212:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
212 | freopen(task ".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
32604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
32604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
32552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
32552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
28508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
28508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
28540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
28540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
28504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
28504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
30548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
30548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
