#include #include #include #include #include #include #include #include #include #include #include using namespace std; using namespace atcoder; using i64 = int64_t; using u64 = uint64_t; using i32 = int32_t; using u32 = uint32_t; #define REP(i, s, t) for (i32 i = (s); i < (t); ++i) template std::vector vec(T elem, int len) { return std::vector(len, elem); } struct HLD { const i32 size; vector> graph; vector left; vector right; vector vertex; vector parent; vector path_root; HLD(const i32 size) : size(size), graph(size), left(size), right(size), vertex(size), parent(size, -1), path_root(size) {} void add_edge(const i32 a, const i32 b) { assert(0 <= min(a, b) && max(a, b) < size); graph[a].emplace_back(b); graph[b].emplace_back(a); } void build(const i32 root) { dfs_size(root, -1); i32 id = 0; path_root[root] = root; dfs_ord(root, id); } i32 dfs_size(const i32 v, const i32 p) { i32 s = 1; i32 max = 0; i32 max_pos = -1; for (i32 i = 0; i < (i32)graph[v].size(); ++i) { const i32 u = graph[v][i]; if (u == p) continue; parent[u] = v; const i32 c = dfs_size(u, v); if (c > max) { max = c; max_pos = i; } s += c; } if (max_pos >= 0) { swap(graph[v][max_pos], graph[v][0]); } return s; } void dfs_ord(const i32 v, i32 &id) { left[v] = id; vertex[id] = v; id += 1; for (i32 i = 0; i < (i32)graph[v].size(); ++i) { const i32 u = graph[v][i]; if (u == parent[v]) continue; if (i == 0) { path_root[u] = path_root[v]; dfs_ord(u, id); } else { path_root[u] = u; dfs_ord(u, id); } } right[v] = id; } pair subtree(const i32 v) { assert(v < size); return make_pair(left[v], right[v]); } i32 next(const i32 s, i32 t) { assert(0 <= min(s, t) && max(s, t) < size && s != t); const auto [x, y] = subtree(s); const auto [z, w] = subtree(t); if (!(x <= z && w <= y)) { return parent[s]; } i32 pre = t; while (path_root[s] != path_root[t]) { pre = path_root[t]; t = parent[pre]; } return t == s ? pre : vertex[x + 1]; } vector> path(i32 s, i32 t) { assert(0 <= min(s, t) && max(s, t) < size && s != t); static pair a[24]; static pair b[24]; i32 x = 0; i32 y = 0; while (path_root[s] != path_root[t]) { if (left[s] < left[t]) { const i32 p = path_root[t]; b[y++] = make_pair(left[p], left[t] + 1); t = parent[p]; } else { const i32 p = path_root[s]; a[x++] = make_pair(left[p], left[s] + 1); s = parent[p]; } } if (left[s] <= left[t]) { b[y++] = make_pair(left[s], left[t] + 1); } else { a[x++] = make_pair(left[t], left[s] + 1); } vector> res(x + y); for (i32 i = 0; i < x; ++i) { res[i] = a[i]; } for (i32 i = 0; i < y; ++i) { res[x + i] = b[y - 1 - i]; } return res; } }; i32 read_int(void) { i32 v; cin >> v; return v; } i64 add(i64 a, i64 b) { return a + b; } i64 zero() { return 0; } template array add(const array a, const array b) { array c; REP(i, 0, K) { c[i] = a[i] + b[i]; } return c; } template array zero() { array c{}; return c; } template array map(const array f, array x) { array res(x); REP(bit, 1, 1 << K) { for (i32 p = bit; p > 0; p = (p - 1) & bit) { i64 v = x[p ^ bit]; REP(i, 0, K) { if ((p >> i) & 1) { v *= f[i]; } } res[bit] += v; } } return res; } void run(void) { const i32 n = read_int() + 1; const i32 q = read_int(); HLD hld(n); hld.add_edge(0, 1); REP(i, 2, n) { const i32 a = read_int(); const i32 b = read_int(); hld.add_edge(a, b); } hld.build(0); segtree cnt(n); lazy_segtree, add, zero, array, map, add, zero> fix_root(n); lazy_segtree, add, zero, array, map, add, zero> move_root(n); REP(i, 1, n) { const i64 v = hld.vertex[i]; const i64 p = hld.parent[v]; move_root.set(i, {v - p, 0, 0, 0}); } vector state(n, 0); REP(i, 0, q) { const i32 u = read_int(); const i32 sign = (state[u] ^ 1) - state[u]; move_root.apply(0, n, {sign, 0}); i32 sub = state[u]; auto path = hld.path(u, 0); for (auto [l, r] : path) { move_root.apply(l, r, {-sign, sign}); const i32 v = hld.vertex[r - 1]; const auto [s, t] = hld.subtree(v); const i32 c = cnt.prod(s, t) - sub; const auto x = fix_root.get(r - 1); fix_root.set(r - 1, {x[0] + sign * v, x[1] + (i64)sign * c * v}); fix_root.apply(l, r - 1, {sign}); const auto [a, b] = hld.subtree(hld.vertex[l]); sub = cnt.prod(a, b); } state[u] ^= 1; cnt.set(hld.left[u], state[u]); const i32 r = read_int(); const i32 v = read_int(); i64 ans = 0; if (hld.left[v] <= hld.left[r] && hld.right[r] <= hld.right[v]) { ans = fix_root.prod(0, n)[1]; const auto path = hld.path(0, v); for (auto [l, r] : path) { ans += move_root.prod(l, r)[3]; } if (r != v) { const i32 x = hld.next(v, r); const auto [s, t] = hld.subtree(x); const i32 c = cnt.prod(0, n); const i32 d = cnt.prod(s, t); ans -= (i64)v * d * (c - d); ans -= fix_root.prod(s, t)[1]; } } else { const auto [l, r] = hld.subtree(v); ans = fix_root.prod(l, r)[1]; } cout << ans << "\n"; } } int main(void) { cin.tie(nullptr); ios::sync_with_stdio(false); run(); return 0; }