\(Solution:\)

法一：LCT裸题

又好想又好码，只不过常数太大。

法二：树链剖分

每次断边将该边权的值++，连边--，然后边权化点权(给儿子)，询问就查询从x到y的路径上的边权和，树状数组套树链剖分维护.

\(Source\)

// luogu-judger-enable-o2#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;namespace io { char buf[1<<21], *pos = buf, *end = buf; inline char getc() { return pos == end && (end = (pos = buf) + fread(buf, 1, 1<<21, stdin), pos == end) ? EOF : *pos ++; } inline int rint() { register int x = 0, f = 1; register char c; while (!isdigit(c = getchar())) if (c == '-') f = -1; while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = getchar())); return x * f; } template
          
            inline bool chkmin(T &x, T y) { return x > y ? (x = y, 0) : 1; } template
           
             inline bool chkmax(T &x, T y) { return x < y ? (x = y, 0) : 1; }#define debug(...) fprintf(stderr, __VA_ARGS__)#define ____ debug("go")#define rep(i, a, b) for (register int i = a; i <= b; ++ i)#define dep(i, a, b) for (register int i = a; i >= b; -- i)#define travel(i, u) for (register int i = head[u]; i; i = nxt[i])#define mem(a, b) memset(a, b, sizeof a)}using io::rint;using io::chkmin;using io::chkmax;const int N = 4e5 + 1;int n, m;int tot, ver[N<<1], head[N], nxt[N<<1];void add(int u, int v) { ver[++tot] = v, nxt[tot] = head[u], head[u] = tot; }int seg[N], size[N], top[N], son[N], cnt, fa[N], dep[N];void DFS1(int x, int f) { fa[x] = f; size[x] = 1; dep[x] = dep[f] + 1; travel(i, x) { if (ver[i] == f) continue; DFS1(ver[i], x); size[x] += size[ver[i]]; if (size[son[x]] < size[ver[i]]) son[x] = ver[i]; }}void DFS2(int u, int topf) { seg[u] = ++cnt; top[u] = topf; if (son[u]) DFS2(son[u], topf); else return; travel(i, u) { if (ver[i] != fa[u] && ver[i] != son[u]) DFS2(ver[i], ver[i]); }}struct BIT { int s[N]; void insert(int x, int c) { for (int i = x; i <= n; i += (i & -i)) s[i] += c; } int query(int x) { int res = 0; for (int i = x; i; i -= (i & -i)) res += s[i]; return res; } } T;vector
            
             
               > War;int Query(int x, int y) { int ans = 0; while (top[x] != top[y]) { if (dep[top[x]] < dep[top[y]]) swap(x, y);//打挂的地方 ans += T.query(seg[x]) - T.query(seg[top[x]] - 1); x = fa[top[x]]; } if (dep[x] < dep[y]) swap(x, y); ans += T.query(seg[x]) - T.query(seg[y]); return ans;}int main() {#ifndef ONLINE_JUDGE freopen("P3950.in", "r", stdin); freopen("P3950.out", "w", stdout);#endif n = rint(); m = rint(); for (int i = 1; i < n; ++ i) { int u = rint(), v = rint(); add(u, v); add(v, u); } DFS1(1, 0); DFS2(1, 1); char op[10]; int x, y; while (m --) { scanf("%s", op); if (op[0] == 'Q') { x = rint(), y = rint(); if (Query(x, y)) puts("No"); else puts("Yes"); } else if (op[0] == 'U') { x = rint(); x --; int u = War[x].first, v = War[x].second; if (seg[u] < seg[v]) swap(u, v); T.insert(seg[u], -1); } else { x = rint(), y = rint(); if (seg[x] < seg[y]) swap(x, y); T.insert(seg[x], 1); War.push_back(make_pair(x, y)); } }}