1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110
| #include <bits/stdc++.h> #define lowbit(x) x&-x using namespace std; typedef pair<int, int> P; const int maxn = 1000000; P war[maxn]; int fa[maxn], dep[maxn], val[maxn], sz[maxn], top[maxn], son[maxn]; int tre[maxn]; int tot; int cntw; int n, m; inline int read() { int ch, x = 0, f = 1;ch = getchar(); while((ch < '0' || ch > '9') && ch != '-') ch = getchar(); ch == '-' ? f = -1, ch = getchar() : 0; while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return f * x; } struct Edge { int to, len, nxt; Edge() {} Edge(int _to, int _len, int _nxt):to(_to), len(_len), nxt(_nxt) {} }E[maxn]; int h[maxn], cnte; int L[maxn], R[maxn]; void update(int x, int add) { for(int i = x;i <= maxn; i += lowbit(i)) tre[i] += add; } int query(int x) { int ans = 0; for(int i = x; i; i -= lowbit(i)) ans += tre[i]; return ans; } inline void add_edge(int u, int v, int w) { E[++cnte] = Edge(v, w, h[u]), h[u] = cnte; E[++cnte] = Edge(u, w, h[v]), h[v] = cnte; } void dfs1(int x) {
sz[x] = 1; dep[x] = dep[fa[x]] + 1; for(int i = h[x]; i; i = E[i].nxt) { int to = E[i].to; if(to == fa[x]) continue; fa[to] = x;val[x] = E[i].len; dfs1(to); sz[x] += sz[to]; if(sz[to] > sz[son[x]]) son[x] = to; }
} void dfs2(int x) { L[x] = ++tot; if(x == son[fa[x]]) top[x] = top[fa[x]]; else top[x] = x; if(son[x]) dfs2(son[x]); for(int i = h[x]; i; i = E[i].nxt) { int to = E[i].to; if(to == fa[x] || to == son[x]) continue; dfs2(to); } R[x] = tot; }
void cut(int x, int y) { if(L[x] < L[y]) swap(x, y); update(L[x], 1); } void connect(int x, int y) { if(L[x] < L[y]) swap(x, y); update(L[x], -1); } int qsum(int x, int y) { int ans = 0; while(top[x] != top[y]) { if(dep[top[x]] < dep[top[y]])swap(x, y); ans += (query(L[x]) - query(L[top[x]] - 1)); x = fa[top[x]]; } if(dep[x] < dep[y])swap(x, y); if (x!=y) ans += (query(L[x]) - query(L[y])); return ans; } signed main() { scanf("%d%d", &n, &m); for(int i = 1; i < n; i++) add_edge(read(), read(), 0); dfs1(1); dfs2(1); for(int i = 1;i <= m; i++) { char s[50]; cin >> s; if(s[0] == 'C') { int u = read(), v = read(); cut(u, v); war[++cntw] = P(u, v); } else if(s[0] == 'U') { int w = read(); connect(war[w].first, war[w].second); } else { if(qsum(read(), read()) != 0) puts("No"); else puts("Yes"); } } return 0; }
|