比赛 |
2024暑假C班集训E |
评测结果 |
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
|
题目名称 |
部落冲突 |
最终得分 |
100 |
用户昵称 |
┭┮﹏┭┮ |
运行时间 |
8.562 s |
代码语言 |
C++ |
内存使用 |
8.93 MiB |
提交时间 |
2024-07-14 08:55:29 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
int n,m;
struct made{
int ver,nx;
}e[N<<1];
int hd[N],tot,cnt,len;
int fa[N],size[N],son[N],dep[N];
int a[N],top[N],dfn[N],rnk[N];
struct Tree{
int l,r,la,f;
#define l(x) t[x].l
#define r(x) t[x].r
#define la(x) t[x].la
#define f(x) t[x].f
}t[N<<2];
void pushup(int x){
f(x) = f(x<<1) | f(x<<1|1);
}
void pushdown(int x){
if(la(x) == -1)return;
la(x<<1) = la(x<<1|1) = la(x);
f(x<<1) = f(x<<1|1) = la(x);
la(x) = -1;
}
void build(int x,int l,int r){
l(x) = l,r(x) = r,la(x) = -1;
if(l == r)return;
int mid = l + r >> 1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
}
void change(int x,int l,int z){
if(l(x) == r(x)){
la(x) = z;
f(x) = z;
return;
}
pushdown(x);
int mid = l(x) + r(x) >> 1;
if(l <= mid)change(x<<1,l,z);
else change(x<<1|1,l,z);
pushup(x);
}
int ask(int x,int l,int r){
if(l <= l(x) && r(x) <= r)return f(x);
pushdown(x);
int mid = l(x) + r(x) >> 1,ans = 0;
if(l <= mid)ans |= ask(x<<1,l,r);
if(r > mid)ans |= ask(x<<1|1,l,r);
return ans;
}
//------------------------------
void add(int x,int y){
tot++;
e[tot].ver = y,e[tot].nx = hd[x],hd[x] = tot;
}
void dfs1(int x){
size[x] = 1;
for(int i = hd[x];i;i = e[i].nx){
int y = e[i].ver;
if(dep[y])continue;
dep[y] = dep[x] + 1;
fa[y] = x;
dfs1(y);
size[x] += size[y];
if(!son[x] || size[y] > size[son[x]])son[x] = y;
}
}
void dfs2(int x,int t){
dfn[x] = ++cnt;
rnk[cnt] = x;
top[x] = t;
if(!son[x])return;
dfs2(son[x],t);
for(int i = hd[x];i;i = e[i].nx){
int y = e[i].ver;
if(y != fa[x] && y != son[x])dfs2(y,y);
}
}
int cal(int x,int y){
int ans = 0;
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]])swap(x,y);
ans |= ask(1,dfn[top[x]],dfn[x]);
x = fa[top[x]];
}
if(x == y)return ans;
if(dep[x] > dep[y])swap(x,y);
ans |= ask(1,dfn[x]+1,dfn[y]);
return ans;
}
int main(){
freopen("lct.in","r",stdin);
freopen("lct.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i = 1;i < n;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
dep[1] = 1;
dfs1(1);dfs2(1,1);
build(1,1,n);
for(int i = 1;i <= m;i++){
char c[2];int x,y;
scanf("%s%d",c,&x);
if(c[0] == 'U')change(1,dfn[a[x]],0);
else if(c[0] == 'C'){
scanf("%d",&y) ;
x = dep[x] < dep[y]?y:x;
a[++len] = x;
change(1,dfn[x],1);
}
else{
scanf("%d",&y);
int ans = cal(x,y);
if(ans == 1)printf("No\n");
else printf("Yes\n");
}
}
return 0;
}