#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
using pii = pair<int, int>;
#define fr first
#define sc second
struct Fenwick
{
int aib[120005];
vector<int> descos;
inline int lsb(int x)
{
return x & -x;
}
void update(int pos, int val)
{
descos.push_back(pos);
while(pos <= 120000)
aib[pos] += val, pos += lsb(pos);
}
int query(int pos)
{
int ans = 0;
while(pos)
ans += aib[pos], pos -= lsb(pos);
return ans;
}
void clean()
{
for(auto i : descos)
while(i <= 120000 && aib[i] != 0)
aib[i] = 0, i += lsb(i);
descos.clear();
}
} ds;
struct Intrebare
{
char ch;
int time, val; //daca e cazu
};
vector<Intrebare> qry[120005];
vector<pii> vec[120005];
bool viz[120005];
int answer[120005], sz[120005];
void dfsz(int nod, int papa)
{
int nsz = 1;
for(auto i : vec[nod])
if(i.fr != papa && !viz[i.fr])
dfsz(i.fr, nod), nsz += sz[i.fr];
sz[nod] = nsz;
}
int find_centroid(int nod, int szmx, int papa)
{
for(auto i : vec[nod])
if(!viz[i.fr] && i.fr != papa && sz[i.fr] >= (szmx + 1) / 2)
return find_centroid(i.fr, szmx, nod);
return nod;
}
int crdcr[120005], spretata[120005]; // &1 daca crescator, &2 daca descrescator
void dfs(int nod, int papa, vector<int> &baga, int primu = 0)
{
if(!primu)
{
//cout << nod << " " << papa << " " << spretata[nod] << " " << spretata[papa] << '\n';
crdcr[nod] = 0;
if(spretata[nod] <= spretata[papa])
crdcr[nod] += (1 & crdcr[papa]);
if(spretata[nod] >= spretata[papa])
crdcr[nod] += (2 & crdcr[papa]);
}
baga.push_back(nod);
for(auto i : vec[nod])
if(!viz[i.fr] && i.fr != papa)
spretata[i.fr] = i.sc, dfs(i.fr, nod, baga, 0);
}
void dfs_centroid(int nod)
{
dfsz(nod, 0);
int centr = find_centroid(nod, sz[nod], 0);
crdcr[centr] = 3;
vector<pair<int, vector<int>>> realvec;
for(auto i : vec[centr])
if(!viz[i.fr])
{
realvec.push_back({i.fr, vector<int>(0)});
spretata[i.fr] = i.sc;
crdcr[i.fr] = 3;
dfs(i.fr, centr, realvec.back().sc, 1);
}
sort(all(realvec), [&](pair<int, vector<int>> a, pair<int, vector<int>> b)
{
return spretata[a.fr] < spretata[b.fr];
});
//cout << centr << ": \n";
map<int, int> papsubctr, pospap;
for(auto i : realvec)
for(auto j : i.sc)
{
papsubctr[j] = i.fr;
// cout << j << " papa: " << i.fr << " spretata: " << spretata[j] << " crdcr: " << crdcr[j] << '\n';
}
// cout << '\n';
for(int i = 0; i < realvec.size(); i ++)
pospap[realvec[i].fr] = i + 1;
for(int sus = realvec.size() - 1; sus >= 0; sus --)
{
auto i = realvec[sus];
ds.update(spretata[i.fr], 1);
if(sus != realvec.size() - 1)
ds.update(spretata[realvec[sus + 1].fr], -1);
for(auto j : i.sc)
for(auto k : qry[j])
{
if(k.ch == 'Q')
{
if(pospap[papsubctr[j]] > pospap[papsubctr[k.val]] && (crdcr[j] & 2) && (crdcr[k.val] & 1) && spretata[j] <= k.time)
answer[k.time] = -2;
// cout << centr << " " << k.ch << " " << j << " " << k.val << " " << k.time << " " << answer[k.time] << '\n';
}
else if(crdcr[j] & 1)
answer[k.time] += ds.query(k.time);
}
for(auto j : i.sc)
if(crdcr[j] & 2)
ds.update(spretata[j], 1);
}
//ar fi cazu sa verificam si pentru centroid queryurile
for(auto k : qry[centr])
{
if(k.ch == 'Q')
{
if(pospap[papsubctr[k.val]] && (crdcr[k.val] & 1) && spretata[papsubctr[k.val]] <= k.time)
answer[k.time] = -2;
}
else
answer[k.time] += ds.query(k.time) + 1; //ca se poate lua si pe el
}
ds.clean();
viz[centr] = true;
for(auto i : vec[centr])
if(!viz[i.fr])
dfs_centroid(i.fr);
}
signed main()
{
int n, q;
cin >> n >> q;
for(int i = 1; i <= q + n - 1; i ++)
{
char ch;
cin >> ch;
if(ch == 'S')
{
int u, v;
cin >> u >> v;
vec[u].push_back({v, i});
vec[v].push_back({u, i});
answer[i] = -1;
}
if(ch == 'Q')
{
int u, v;
cin >> u >> v;
qry[u].push_back({'Q', i, v});
answer[i] = -3;
}
if(ch == 'C')
{
int u;
cin >> u;
qry[u].push_back({'C', i, 0});
}
}
dfs_centroid(1);
for(int i = 1; i <= q + n - 1; i ++)
if(answer[i] != -1)
{
if(answer[i] >= 0)
cout << answer[i] + 1 << '\n';
else if(answer[i] == -2)
cout << "yes\n";
else
cout << "no\n";
}
}
/*
6 9
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5
C 1
C 2
C 3
C 4
C 5
C 6
*/
Compilation message
servers.cpp: In function 'void dfs_centroid(int)':
servers.cpp:121:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int i = 0; i < realvec.size(); i ++)
| ~~^~~~~~~~~~~~~~~~
servers.cpp:128:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | if(sus != realvec.size() - 1)
| ~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
10320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
10320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
10312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
10312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
10388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
10388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
10312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
10312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
10312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
10312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
10312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
10312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
