树剖板子题。
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<stack> 9 #include<queue> 10 #include<vector> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a, x) memset(a, x, sizeof(a)) 15 #define rg register 16 typedef long long ll; 17 typedef double db; 18 const int INF = 0x3f3f3f3f; 19 const db eps = 1e-8; 20 const int maxn = 3e5 + 5; 21 inline ll read() 22 { 23 ll ans = 0; 24 char ch = getchar(), las = ' '; 25 while(!isdigit(ch)) las = ch, ch = getchar(); 26 while(isdigit(ch)) ans = ans * 10 + ch - '0', ch = getchar(); 27 if(las == '-') ans = -ans; 28 return ans; 29 } 30 inline void write(ll x) 31 { 32 if(x < 0) putchar('-'), x = -x; 33 if(x >= 10) write(x / 10); 34 putchar(x % 10 + '0'); 35 } 36 37 int n, m; 38 struct Edge 39 { 40 int to, nxt; 41 }e[maxn << 1]; 42 int head[maxn], ecnt = 0; 43 void addEdge(int x, int y) 44 { 45 e[++ecnt].to = y; 46 e[ecnt].nxt = head[x]; 47 head[x] = ecnt; 48 } 49 50 int dep[maxn], fa[maxn], siz[maxn], son[maxn]; 51 void dfs1(int now, int f) 52 { 53 siz[now] = 1; 54 for(int i = head[now]; i; i = e[i].nxt) 55 { 56 if(e[i].to == f) continue; 57 dep[e[i].to] = dep[now] + 1; 58 fa[e[i].to] = now; 59 dfs1(e[i].to, now); 60 siz[now] += siz[e[i].to]; 61 if(!son[now] || siz[e[i].to] > siz[son[now]]) son[now] = e[i].to; 62 } 63 } 64 int top[maxn], dfsx[maxn], cnt = 0; 65 void dfs2(int now, int f) 66 { 67 dfsx[now] = ++cnt; 68 if(son[now]) 69 { 70 top[son[now]] = top[now]; 71 dfs2(son[now], now); 72 } 73 for(int i = head[now]; i; i = e[i].nxt) 74 { 75 if(e[i].to == f || e[i].to == son[now]) continue; 76 top[e[i].to] = e[i].to; 77 dfs2(e[i].to, now); 78 } 79 } 80 81 int l[maxn << 2], r[maxn << 2], sum[maxn << 2]; 82 void build(int L, int R, int now) 83 { 84 l[now] = L; r[now] = R; 85 if(L == R) return; 86 int mid = (L + R) >> 1; 87 build(L, mid, now << 1); 88 build(mid + 1, R, now << 1 | 1); 89 } 90 void update(int idx, int now) 91 { 92 if(l[now] == r[now]) {sum[now] ^= 1; return;} 93 int mid = (l[now] + r[now]) >> 1; 94 if(idx <= mid) update(idx, now << 1); 95 else update(idx, now << 1 | 1); 96 sum[now] = sum[now << 1] + sum[now << 1 | 1]; 97 } 98 bool query(int L, int R, int now) 99 { 100 if(L == l[now] && R == r[now]) return sum[now]; 101 int mid = (l[now] + r[now]) >> 1; 102 if(R <= mid) return query(L, R, now << 1); 103 else if(L > mid) return query(L, R, now << 1 | 1); 104 else return query(L, mid, now << 1) | query(mid + 1, R, now << 1 | 1); 105 } 106 107 bool query_path(int x, int y) 108 { 109 while(top[x] != top[y]) 110 { 111 if(dep[top[x]] < dep[top[y]]) swap(x, y); 112 if(query(dfsx[top[x]], dfsx[x], 1)) return 0; 113 x = fa[top[x]]; 114 } 115 if(dfsx[x] > dfsx[y]) swap(x, y); 116 if(x == y) return 1; 117 return query(dfsx[x] + 1, dfsx[y], 1) ^ 1; 118 } 119 120 int war[maxn], wcnt = 0; 121 char c[2]; 122 123 int main() 124 { 125 n = read(); m = read(); 126 for(int i = 1; i < n; ++i) 127 { 128 int x = read(), y = read(); 129 addEdge(x, y); addEdge(y, x); 130 } 131 dfs1(1, 0); top[1] = 1; dfs2(1, 0); 132 build(1, cnt, 1); 133 for(int i = 1; i <= m; ++i) 134 { 135 scanf("%s", c); 136 if(c[0] == 'Q') 137 { 138 int x = read(), y = read(); 139 printf("%s ", query_path(x, y) ? "Yes" : "No"); 140 } 141 else if(c[0] == 'C') 142 { 143 int x = read(), y = read(); 144 if(dfsx[x] < dfsx[y]) swap(x, y); 145 war[++wcnt] = x; 146 update(dfsx[x], 1); 147 } 148 else 149 { 150 int x = read(); 151 update(dfsx[war[x]], 1); 152 } 153 } 154 return 0; 155 }