题意：
给一棵树，树的每条边有一种颜色，黑色或白色，一开始所有边均为黑色，有两个操作：
操作1：将第i条边变成白色或将第i条边变成黑色。
操作2 ：询问u，v两点之间仅经过黑色变的最短距离。
树链剖分+树状数组
学习树链剖分：
/*
树链剖分：
划分轻重链，效果是将一颗树变成了若干段连续的区间。
向上记录边权
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std; const int MAX = ;
//子树结点数,所在链链头,同链儿子,结点深度,节点在区间的位置,父节点
int siz[MAX], top[MAX], son[MAX], dep[MAX], w[MAX], fa[MAX];
//链式前向星记录一颗树
struct Edge {
int v, ne, id;
} edge[MAX << ]; int head[MAX], cnt, num;
int vis[MAX], pos[MAX];;
//第一次dfs,提取基本信息,划分轻重链
void Dfs1 (int u, int v) {
fa[v] = u, dep[v] = dep[u] + ;
siz[v] = ;
vis[v] = ;
int tem = , p = -;
for (int i = head[v]; i != ; i = edge[i].ne) {
int kid = edge[i].v;
if (!vis[kid]) {
Dfs1 (v, kid);
siz[u] += siz[kid];
if (tem < siz[kid]) tem = siz[kid], p = kid;
}
}
son[v] = p;
}
//第二次DFS,将重链映射到区间
void Dfs2 (int h, int v) {
top[v] = h;
w[v] = ++num;
vis[v] = ;
if (son[v] != -) Dfs2 (h, son[v]);
for (int i = head[v]; i != ; i = edge[i].ne) {
int kid = edge[i].v;
if (son[v] != kid && !vis[kid])
Dfs2 (kid, kid);
pos[edge[i].id] = w[kid]; //边映射到下结点
}
} void addE (int u, int v, int num) {
edge[++cnt].v = v, edge[cnt].id = num;
edge[cnt].ne = head[u], head[u] = cnt;
} int A[MAX]; //pos为边的新编号
void add (int x, int k) {
for (; x <= num; x += x & -x) A[x] += k;
}
int getsum (int x) {
int s = ;
for (; x > ; x -= x & -x) s += A[x];
return s;
}
void modify (int x, int k) {
x = pos[x];
int sta = getsum (x) - getsum (x - );
if (sta == k) return;
else add (x, k - sta);
} void query (int u, int v) {
int s = , f1 = top[u], f2 = top[v], len = ;
while (f1 != f2) {
if (dep[f1] < dep[f2]) {
int y = w[v], x = w[f2];
if (f2 != v) {
if (s += getsum (y) - getsum (x) ) break;
v = f2;
len += y - x;
}
if (s += getsum (x) - getsum (x - ) ) break;
v = fa[v], f2 = top[v];
len++;
}
else {
int y = w[u], x = w[f1];
if (f1 != u) {
if (s += getsum (y) - getsum (x) ) break;
u = f1;
len += y - x;
}
if (s += getsum (x) - getsum (x - ) ) break;
u = fa[u], f1 = top[u];
len++;
}
}
int y = w[v], x = w[u];
s += getsum (max (y, x) ) - getsum (min (y, x) );
len += abs (y - x);
printf ("%d\n", s == ? len : -);
}
int n, u, v, m, t;
int main() {
scanf ("%d", &n);
for (int i = ; i < n; i++) {
scanf ("%d %d", &u, &v);
addE (u, v, i), addE (v, u, i);
}
Dfs1 (, );
memset (vis, , sizeof vis);
Dfs2 (, );
scanf ("%d", &m);
int k, l, r,tol=;
for (int i = ; i <= m; i++) {
scanf ("%d", &k);
if (k != ) {
scanf ("%d", &t);
modify (t, k == ? : );
}
if (k == ) {
scanf ("%d %d", &l, &r);
query (l, r);
} }
}