大致题意：
爱丽丝得到一棵树，树上有n个节点，索引从1到n。树上的每条边可以是黑色或白色，所有的边最初都是白色的。有三种操作： 1. 将一条边的颜色改为黑色。2. 将一条边的颜色改为白色。3. 3.给定一个节点索引，计算从所有奇数节点到该节点的简单路径上的黑色边的数量之和。请注意，简单路径是指两个节点之间的路径，该路径对任何节点的访问都不超过一次。读入一个n和一个m，紧接着读入n-1行，每行两个节点u，v表示u和v有连边，第几行就表示是第几个边。读入m个询问，询问如提议所示。
解题思路：
发现如果有一条边从白色变成了黑色，我们可以认为黑的边把这个树分成了左右两个部分，右边的任意一个点到右边的任意一个点的简单路径都不会经过这个黑色的边，也就是说左边的点无法对左边的点造成任何贡献，右边的点无法对右边的点造成任何贡献。但是左边的点和右边的点可能会有贡献。如果我们知道左边的奇数的点的数量是x1,右边的奇数点的数量为x2，那么右边所有点被奇数点的拜访且经过黑色边的次数就会增加x1的数量，左边所有点被奇数点拜访的数量且经过黑色边的次数都会加x2。所以考虑用线段树维护每个点答案即可。树上跑dfs序建线段树，统计出每个点的子树大小和深度和子树有多少奇数结点。对于第x条边我们可以知道第x个边对应的两个点是谁，我们已经预处理求出深度最大的那个点中有多少奇数点数量sum，那么深度小的那个点对应的奇数结点数量就是(n + 1) / 2 - sum，sum就是我们说的x1, (n + 1) / 2 - sum 就是说的x2。需要注意的地方就是需要开一个数组记录当前边的颜色，如果把一个白色边染成白色或者把一个黑色边染成黑色是不会对答案造成任何影响的。
#include <bits/stdc++.h>
const int N = 1e5 + 10;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using ll = long long;
typedef std::pair<int, int> PII;
int a[N];
int n, m;
int h[N], ne[N << 1], e[N << 1], idx;
int sz[N], fa[N], id[N], rid[N], timedelta, dep[N], odd[N];
bool color[N];
inline void add(int a, int b) {
ne[idx] = h[a], e[idx] = b, h[a] = idx ++;
}
inline void dfs(int u, int father, int depth) {
id[u] = ++ timedelta, rid[timedelta] = u;
sz[u] = 1; dep[u] = depth;
if (u & 1) odd[u] = 1;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == father) continue;
dfs(j, u, depth + 1);
sz[u] += sz[j];
odd[u] += odd[j];
}
}
struct node {
ll ans, tag;
}tr[N << 2];
#define ls u << 1
#define rs u << 1 | 1
inline void pushdown(int u) {
if (tr[u].tag) {
tr[ls].tag += tr[u].tag;
tr[rs].tag += tr[u].tag;
tr[ls].ans += tr[u].tag;
tr[rs].ans += tr[u].tag;
tr[u].tag = 0;
}
}
inline void modify(int u, int L, int R, int l, int r, int v, int how) {
if (L >= l && R <= r) {
if (how) {
if (L == R) tr[u].ans += v;
else tr[u].tag += v;
} else {
if (L == R) tr[u].ans -= v;
else tr[u].tag -= v;
}
return ;
}
pushdown(u);
int mid = L + R >> 1;
if (l <= mid) modify(ls, L, mid, l, r, v, how);
if (r > mid) modify(rs, mid + 1, R, l, r, v, how);
}
inline ll query(int u, int L, int R, int x) {
if (L == R) return tr[u].ans;
pushdown(u);
int mid = L + R >> 1;
if (x <= mid) return query(ls, L, mid, x);
return query(rs, mid + 1, R, x);
}
inline void solve() {
memset(h, -1, sizeof h);
std::cin >> n >> m;
std::vector<PII> edge;
for (int i = 2; i <= n; i ++) {
int a, b;
std::cin >> a >> b;
add(a, b);
add(b, a);
edge.push_back({a, b});
}
int tot = n + 1 >> 1; // 编号为奇数的点的个数
dfs(1, -1, 1);
while (m --) {
int op, x;
std::cin >> op >> x;
if (op == 2) { // 染成黑色
x --;
if (!color[x]) continue;
color[x] = false;
auto [u, v] = edge[x];
if (dep[u] < dep[v]) std::swap(u, v);
int top = tot - odd[u];
modify(1, 1, n, id[u], id[u] + sz[u] - 1, top, 0);
if (id[u] > 1)
modify(1, 1, n, 1, id[u] - 1, odd[u], 0);
if (id[u] + sz[u] <= n)
modify(1, 1, n, id[u] + sz[u], n, odd[u], 0);
} else if (op == 1) { // 染成白色
x --;
if (color[x]) continue;
color[x] = true;
auto [u, v] = edge[x];
if (dep[u] < dep[v]) std::swap(u, v);
int top = tot - odd[u];
modify(1, 1, n, id[u], id[u] + sz[u] - 1, top, 1);
if (id[u] > 1)
modify(1, 1, n, 1, id[u] - 1, odd[u], 1);
if (id[u] + sz[u] - 1 < n)
modify(1, 1, n, id[u] + sz[u], n, odd[u], 1);
} else { // 求答案
std::cout << query(1, 1, n, id[x]) << '\n';
}
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int _ = 1;
//std::cin >> _;
while (_ --) solve();
return 0;
}