比赛 |
2024暑假C班集训E |
评测结果 |
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
|
题目名称 |
部落冲突 |
最终得分 |
30 |
用户昵称 |
darkMoon |
运行时间 |
6.705 s |
代码语言 |
C++ |
内存使用 |
16.28 MiB |
提交时间 |
2024-07-14 10:49:21 |
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
// #define fin cin
// #define fout cout
ifstream fin("lct.in");
ofstream fout("lct.out");
auto mread = [](){
int x;
fin >> x;
return x;
};
const int N = 3e5 + 5;
int n = mread(), m = mread(), s[N], siz[N], top[N], son[N], dfn[N], d[N], idx, rnk[N], w[N], now, fa[N];
vector<int> v[N];
void add(int x, int k){
while(x <= n){
s[x] += k;
x += x & -x;
}
return;
}
int query(int x){
int ans = 0;
while(x){
ans += s[x];
x -= x & -x;
}
return ans;
}
void dfs1(int x, int fa2){
// printf("*** %d\n", x);
siz[x] = 1;
int ma = 0, p = 0;
for(int y : v[x]){
if(y == fa2){
continue;
}
fa[y] = x;
d[y] = d[x] + 1;
dfs1(y, x);
siz[x] += siz[y];
if(siz[y] > ma){
ma = siz[y], p = y;
}
}
if(ma){
son[x] = p;
}
return;
}
void dfs2(int x, int fa2){
if(x != 1){
dfn[x] = ++idx;
rnk[idx] = x;
}
if(son[x]){
top[son[x]] = top[x];
dfs2(son[x], x);
}
for(int y : v[x]){
if(y == fa2 || y == son[x]){
continue;
}
top[y] = y;
dfs2(y, x);
}
return;
}
int lca(int l, int r){
if(d[l] < d[r]){
swap(l, r);
}
while(top[l] != top[r]){
if(d[top[l]] >= d[top[r]]){
l = fa[top[l]];
}
else{
r = fa[top[r]];
}
}
if(d[l] <= d[r]){
return l;
}
else{
return r;
}
}
int makeAns(int l, int r){
int ans = 0;
int mid = lca(l, r);
// printf("--- %d %d %d\n", l, r, mid);
if(mid != l){
while(top[l] != top[mid]){
ans += query(dfn[l]) - query(fa[dfn[top[l]]]);
l = fa[top[l]];
}
ans += query(dfn[l]) - query(dfn[mid]);
// printf("### %d %d %d %d\n", dfn[l], dfn[mid], query(dfn[l]), query(dfn[top[l]]));
}
if(mid != r){
while(top[r] != top[mid]){
ans += query(dfn[r]) - query(dfn[fa[top[r]]]);
r = fa[top[r]];
}
ans += query(dfn[r]) - query(dfn[mid]);
// printf("### %d %d %d %d\n", dfn[r], dfn[mid], query(dfn[r]), query(dfn[top[r]]));
}
return ans;
}
signed main(){
for(int i = 1, x, y; i < n; i ++){
x = mread(), y = mread();
v[x].push_back(y);
v[y].push_back(x);
}
top[1] = 1;
d[1] = 1;
dfs1(1, 0);
// for(int i = 1; i <= n; i ++){
// printf("%d ", rnk[i]);
// }
dfs2(1, 0);
// printf("\n");
while(m --){
char c;
fin >> c;
if(c == 'Q'){
int p = mread(), q = mread();
fout << (makeAns(p, q) == 0 ? "Yes" : "No") << "\n";
}
else if(c == 'C'){
int p = mread(), q = mread();
if(d[p] > d[q]){
swap(p, q);
}
add(dfn[q], 1);
// printf("*** %d\n", dfn[q]);
w[++now] = dfn[q];
}
else{
int x = mread();
add(w[x], -1);
}
}
return 0;
}