题意
别人今天期中考，而你依然在机房里为今年的 NOIP 努力刷题。
一道两道三四道，紫题黑题不会题。
暴力枚举TLE，数组开小爆零寄……
已过立冬，窗外寒风瑟瑟，但是你看到有一棵树屹立不倒，你也想成为像大树一般挺拔的人。
一、二、三……你仔细数着，发现树上有 \(n\) 个结点。
忽然你手里多出了一个东西，鼓鼓的，原来是一个大小为 \(m\) 的集合。集合里有什么呢？你思索着，打开了集合。原来集合里鼓鼓囊囊装着 \(m\) 条树上的路径。这真是一棵神奇的树呢。你瞅了瞅集合外包装，说明上表明这是由 yzh 公司研发的可重集合，真是个新鲜玩意呢。
“你好啊，OIer！”那棵树朝你说道，“我们来玩个游戏吧。”你当然答应下来。
“游戏有 \(q\) 轮。”竟然是 \(q\) 轮，而不是 \(q^{\sqrt{e}!}\) 轮或者 \(e^{iq\pi}\) 轮，真是有趣呢，你想道。
“每次我可以向你手上的集合里塞入新的一条路径……”这就是它的魔力吗？
“或者我给你一条路径，你要告诉我它完全包含了集合中多少条路径，怎么样？”你爽快答应下来了，真是一个好玩的游戏呢。思索片刻，你发现这竟然和你最近做的题目有些相像……
形式化题意：
一棵 \(n\) 个结点的树，你需要维护路径可重集 \(S\)，初始有 \(m\) 条路径。有 \(q\) 次操作：
- 查询路径 \((u, v)\) 完全包含 \(S\) 中多少条路径；
- 向 \(S\) 中插入一条路径；
- 向 \(S\) 中删除一条路径。
\(n, m, q \leq 10^5\)，保证路径不是一个点，没有第三种操作。事实上，正解可以处理每条路径具有不同权值，删除即为贡献 \(-1\)。
题目分析
考虑 \(p=(u, v)\) 完全包含 \(p'=(u', v')\) 的充要条件。不妨跑出每个节点的 dfn：\(L_u, R_u\)，并且令 \(L_u \leq L_v\) 且 \(L_{u'} \leq L_{v'}\)。分类讨论一下 \(p'\) 的形态：
- 若 \(\operatorname{lca}(u', v') \not \in \{u', v'\}\)，即 \(p'\) 为折链。
发现 \(u\) 需要在 \(u'\) 的子树里，\(v\) 在 \(v'\) 的子树里。可以用 dfn 判断子树包含关系，即 \(u \in \operatorname{subtree}(v) \Leftrightarrow L_u \in [L_v, R_v]\)。 - 若 \(\operatorname{lca}(u', v') = u' \in \{u', v'\}\)，即 \(p'\) 为直链。
那么需要 \(p\) 的其中一端在 \(v'\) 的子树里。对于另一端的限制，我们首先找到 \(u'\) 的一个孩子 \(w\)，满足 \(v' \in \operatorname{subtree}(w)\)，那么另一端需要在除了 \(\operatorname{subtree}(w)\) 的结点中。我们可以画图帮助理解：
\(p\) 的一端在蓝色部分中，另一端在绿色部分中。我们钦定了 \(L_u \leq L_v\)，所以这里可以分成不重复的两部分：\(L_u \in [1, L_w) \land L_v \in [L_{v'}, R_{v'}]\) 或 \(L_u \in [L_{v'}, R_{v'}] \land L_v \in (R_w, n]\)。
于是，我们发现一条 \(S\) 中的路径对之后查询产生的贡献，可以表示为 \(L_u\) 上一段区间和 \(L_v\) 上一段区间。将二元组放到二维笛卡尔坐标系上，将问题转化为了如下形式：
动态往平面里插入带权矩形，查询包含某一个点的矩形权值和。
对于静态问题，直接扫描线。此题使用树套树，或者 CDQ 分治。可不要小瞧树套树！要是强制在线，只能老老实实做数据结构喽。
代码
树套树
CDQ 分治
#pragma GCC optimize("Ofast", "inline", "omit-frame-pointer", "no-stack-protector", "fast-math", "unroll-loops")
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 1 << 26;
char buf[MAX], *ip = buf, obuf[MAX], *op = obuf;
#define putchar(x) *op++ = x
template <typename T>
inline void read(T &x) {
x = 0; char ch = *ip++;
for (; ch < 48; ch = *ip++);
for (; ch >= 48; ch = *ip++) x = (x << 3) + (x << 1) + (ch ^ 48);
}
template <typename T>
inline void write(T x) {
static short stack[20], top(0);
do stack[++top] = x % 10; while (x /= 10);
while (top) putchar(stack[top--] | 48);
}
const int N = 100005;
const int lgN = __lg(N) + 1;
int n, m, q;
vector<int> edge[N];
int dpt[N], fa[N], st[lgN][N];
int L[N], R[N], timer;
void dfs(int u) {
st[0][L[u] = ++timer] = u;
for (int v : edge[u]) if (v != fa[u]) dpt[v] = dpt[u] + 1, fa[v] = u, dfs(v);
R[u] = timer;
}
inline int Min(int u, int v) { return dpt[u] < dpt[v] ? u : v; }
// when dpt[u] == dpt[v], returns v
inline int plca(int u, int v) {
// requires L[u] < L[v], u != v
int p = __lg((v = L[v]) - (u = L[u])++);
return Min(st[p][u], st[p][v - (1 << p) + 1]);
}
struct Line {
int y, lx, rx, v;
} line[N << 3];
int lineCnt, qryCnt, ans[N];
inline void insert(int Lu, int Ru, int Lv, int Rv) {
if (Lu > Ru || Lv > Rv) return;
line[++lineCnt] = { Lv, Lu, Ru, 1 };
line[++lineCnt] = { Rv + 1, Lu, Ru, -1 };
}
inline void pathInsert(int u, int v) {
if (L[u] > L[v]) u ^= v ^= u ^= v;
int fp = plca(u, v), p = fa[fp];
if (u == p) {
// straight path
insert(1, L[fp] - 1, L[v], R[v]);
insert(L[v], R[v], R[fp] + 1, n);
} else {
// common path
insert(L[u], R[u], L[v], R[v]);
}
}
inline void qryInsert(int idx, int u, int v) {
if (L[u] > L[v]) u ^= v ^= u ^= v;
line[++lineCnt] = { L[v], L[u], idx, 0 };
}
int tree[N];
inline void modify(int p, int v) { for (; p <= n; p += p & -p) tree[p] += v; }
inline int query(int p) {
int res = 0;
for (; p; p &= p - 1) res += tree[p];
return res;
}
inline void modify(int l, int r, int v) { modify(l, v), modify(r + 1, -v); }
void solve(int l, int r) {
if (l == r) return;
int mid = (l + r) >> 1;
solve(l, mid), solve(mid + 1, r);
int p = l - 1;
for (int q = mid + 1; q <= r; ++q) {
while (p + 1 <= mid && line[p + 1].y <= line[q].y)
if (line[++p].v) modify(line[p].lx, line[p].rx, line[p].v);
if (line[q].v == 0) ans[line[q].rx] += query(line[q].lx);
}
for (; p >= l; --p) if (line[p].v) modify(line[p].lx, line[p].rx, -line[p].v);
inplace_merge(line + l, line + mid + 1, line + r + 1,
[] (const Line& a, const Line& b) -> bool {
return a.y < b.y;
}
);
}
// divide solved time order
// inplace_merge solved Y order
// data structure solved X order
signed main() {
#ifndef XuYueming
freopen("revolt.in", "r", stdin);
freopen("revolt.out", "w", stdout);
#endif
fread(buf, 1, MAX, stdin), read(n), read(m), read(q);
for (int i = 1, u, v; i < n; ++i) {
read(u), read(v);
edge[u].emplace_back(v);
edge[v].emplace_back(u);
}
dfs(1);
for (int k = 1; k < lgN; ++k)
for (int i = 1; i + (1 << k) - 1 <= n; ++i)
st[k][i] = Min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
for (int u, v; m--; ) read(u), read(v), pathInsert(u, v);
for (int op, u, v; q--; ) {
read(op), read(u), read(v);
if (op == 1) qryInsert(++qryCnt, u, v);
else pathInsert(u, v);
}
solve(1, lineCnt);
for (int i = 1; i <= qryCnt; ++i) write(ans[i]), putchar('\n');
fwrite(obuf, 1, op - obuf, stdout);
return 0;
}