#include <iostream> #include <vector> using namespace std; const int N = 3e4 + 10; int n, x, y; int q, type, t1, t2; int sz[N], ChainID[N], ChainHead[N]; int in[N], out[N], par[N]; int CurChain = 1, CurPos; vector <int> v[N]; int calc_size(int s = 1, int p = -1) { sz[s] = 1; for (int z: v[s]) { if (z == p) continue; par[z] = s; sz[s] += calc_size(z, s); } return sz[s]; } void HLD(int s = 1) { if (!ChainHead[CurChain]) { ChainHead[CurChain] = s; } ChainID[s] = CurChain; in[s] = out[s] = ++CurPos; int nxt = 0; for (int z: v[s]) { if (z == par[s]) continue; if (sz[z] > sz[nxt]) nxt = z; } if (!nxt) return; HLD(nxt); out[s] = out[nxt]; for (int z: v[s]) { if (z == par[s] || nxt == z) continue; ++CurChain; HLD(z); out[s] = out[z]; } } struct BIT { int val[N]; BIT () { fill_n(val, N, 0); } void update(int u, int VAL) { while (u <= n) { val[u] += VAL; u += u & -u; } } int get(int u) { int res = 0; while (u > 0) { res += val[u]; u -= u & -u; } return res; } int range(int l, int r) { return get(r) - get(l - 1); } }; vector <BIT> bit[21]; void UPDATE(int A, int B, int val) { vector <int> one, two; while (!(in[A] <= in[B] && out[A] >= in[B])) { one.push_back(A); A = par[A]; } one.push_back(A); while (B != A) { two.push_back(B); B = par[B]; } while (!two.empty()) { one.push_back(two.back()); two.pop_back(); } int len = one.size(); for (int i = 0; i < len; ++i) { bit[len][i].update(in[one[i]], val); } } int GetPath(int A, int B, int len, int mod) { int res = 0; while (ChainID[A] != ChainID[B]) { if (ChainID[A] < ChainID[B]) swap(A, B); res += bit[len][mod].range(in[ChainHead[ChainID[A]]], in[A]); A = par[ChainHead[ChainID[A]]]; } if (in[A] > in[B]) swap(A, B); res += bit[len][mod].range(in[A], in[B]); return res; } int Left(int l, int num, int mod) { int ret = (int)(l / num) * num + mod; if (ret < l) ret += num; return ret; } int Right(int r, int num, int mod) { int ret = (int)(r / num) * num + mod; if (ret > r) ret -= num; return ret; } int main() { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); cin >> n; for (int i = 1; i < n; ++i) { cin >> x >> y; v[x].push_back(y); v[y].push_back(x); } calc_size(); HLD(); for (int i = 1; i <= 20; ++i) { bit[i].resize(i); } cin >> q; while (q--) { cin >> x >> y; UPDATE(x, y, 1); } cin >> q; while (q--) { cin >> type >> x >> y; if (type == 1) UPDATE(x, y, 1); else if (type == 2) UPDATE(x, y, -1); else { cin >> t1 >> t2; long long ans = 0; for (int len = 1; len <= 20; ++len) { for (int mod = 0; mod < len; ++mod) { int LEFT = Left(t1, len, mod), RIGHT = Right(t2, len, mod); if (LEFT > RIGHT) continue; int one = GetPath(x, y, len, mod); int two = (RIGHT - LEFT) / len + 1; ans += 1ll * one * two; } } cout << ans << "\n"; } } return 0; }