哪位好心大佬帮蒟蒻看看/kk

我先睡了

command_block大佬的两个hack都过了，数据下载不了

亲测define int long long无效

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
const int inf = 0x3f3f3f3f;
int n, m, head[N], to[N << 1], nxt[N << 1], tot;
int dep[N], fa[N], sz[N], son[N], id[N], top[N], pos[N], cnt;
int from[N << 1], to2[N << 1], totColor;
int g[N][20];
inline void link(int u, int v)
{
    to[tot] = v;
    nxt[tot] = head[u];
    head[u] = tot++;
}
inline int toSameDepth(int x, int y)
{
    for (int i = 18; i >= 0; i--)
        if (dep[g[x][i]] > dep[y])
            x = g[x][i];
    return x;
}
inline int LCA(int x, int y)
{
    while (top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y])
        swap(x, y);
    return x;
}
namespace SegTree
{
    int t[N << 2], tag[N << 2], mx[N << 2], col[N << 2];
    inline int ls(int p)
    {
        return p << 1;
    }
    inline int rs(int p)
    {
        return p << 1 | 1;
    }
    inline void push_up(int p)
    {
        mx[p] = max(mx[ls(p)], mx[rs(p)]);
    }
    inline void push_down(int p)
    {
        if (tag[p])
        {
            mx[ls(p)] += tag[p];
            mx[rs(p)] += tag[p];
            tag[ls(p)] += tag[p];
            tag[rs(p)] += tag[p];
            tag[p] = 0;
        }
        if (col[p])
        {
            col[ls(p)] = col[rs(p)] = col[p];
            col[p] = 0;
        }
    }
    inline void build(int p, int l, int r)
    {
        if (l == r)
        {
            mx[p] = dep[pos[l]];
            col[p] = pos[l];
            return;
        }
        int mid = l + r >> 1;
        build(ls(p), l, mid);
        build(rs(p), mid + 1, r);
        push_up(p);
    }
    inline int queryMax(int p, int l, int r, int qx, int qy)
    {
        if (qx <= l && r <= qy)
            return mx[p];
        push_down(p);
        int res = -inf, mid = l + r >> 1;
        if (qx <= mid)
            res = max(res, queryMax(ls(p), l, mid, qx, qy));
        if (mid < qy)
            res = max(res, queryMax(rs(p), mid + 1, r, qx, qy));
        return res;
    }
    inline int queryColor(int p, int l, int r, int x)
    {
        if (l == r)
            return col[p];
        push_down(p);
        int mid = l + r >> 1;
        if (x <= mid)
            return queryColor(ls(p), l, mid, x);
        else
            return queryColor(rs(p), mid + 1, r, x);
    }
    inline void add(int p, int l, int r, int dl, int dr, int k)
    {
        if (dl <= l && r <= dr)
        {
            tag[p] += k;
            mx[p] += k;
            return;
        }
        push_down(p);
        int mid = l + r >> 1;
        if (dl <= mid)
            add(ls(p), l, mid, dl, dr, k);
        if (mid < dr)
            add(rs(p), mid + 1, r, dl, dr, k);
        push_up(p);
    }
    inline void updateColor(int p, int l, int r, int dl, int dr, int k)
    {
        if (dl <= l && r <= dr)
        {
            col[p] = k;
            return;
        }
        push_down(p);
        int mid = l + r >> 1;
        if (dl <= mid)
            updateColor(ls(p), l, mid, dl, dr, k);
        if (mid < dr)
            updateColor(rs(p), mid + 1, r, dl, dr, k);
    }
}
namespace HLD
{
    inline void dfs1(int x, int f, int d)
    {
        fa[x] = f;
        dep[x] = d;
        sz[x] = 1;
        from[x] = to2[x] = x;
        g[x][0] = f;
        for (int i = 1; i <= 18; i++)
            g[x][i] = g[g[x][i - 1]][i - 1];
        for (int i = head[x]; ~i; i = nxt[i])
            if (to[i] != f)
            {
                dfs1(to[i], x, d + 1);
                sz[x] += sz[to[i]];
                if (sz[to[i]] > sz[son[x]])
                    son[x] = to[i];
            }
    }
    inline void dfs2(int x, int tp)
    {
        id[x] = ++cnt;
        top[x] = tp;
        pos[cnt] = x;
        if (!son[x])
            return;
        dfs2(son[x], tp);
        for (int i = head[x]; ~i; i = nxt[i])
            if (to[i] != fa[x] && to[i] != son[x])
                dfs2(to[i], to[i]); // new begin
    }
    inline int rangeSum(int x, int y)
    {
        int lca = LCA(x, y);
        return SegTree::queryMax(1, 1, n, id[x], id[x]) + SegTree::queryMax(1, 1, n, id[y], id[y]) - (SegTree::queryMax(1, 1, n, id[lca], id[lca]) << 1) + 1;
    }
    inline int treeMax(int x)
    {
        return SegTree::queryMax(1, 1, n, id[x], id[x] + sz[x] - 1);
    }
    inline void upd(int x, int y, int last)
    {
        while (top[x] != top[y])
        {
            if (dep[top[x]] < dep[top[y]])
                swap(x, y);
            int tmp = SegTree::queryMax(1, 1, n, id[x], id[y]);
            SegTree::add(1, 1, n, id[top[x]], id[top[x]] + sz[top[x]] - 1, 1 - tmp);
            if (last)
                SegTree::add(1, 1, n, id[last], id[last] + sz[last] - 1, tmp - 1);
            SegTree::updateColor(1, 1, n, id[top[x]], id[x], totColor);
            last = top[x];
            x = fa[top[x]];
        }
        if (dep[x] > dep[y])
            swap(x, y);
        int tmp = SegTree::queryMax(1, 1, n, id[x], id[x]);
        SegTree::add(1, 1, n, id[x], id[x] + sz[x] - 1, 1 - tmp);
        if (last)
            SegTree::add(1, 1, n, id[last], id[last] + sz[last] - 1, tmp - 1);
        SegTree::updateColor(1, 1, n, id[x], id[y], totColor);
    }
    inline void update(int x)
    {
        from[++totColor] = x;
        to2[totColor] = 1;
        int last = 0;
        while (x)
        {
            int tmp = SegTree::queryColor(1, 1, n, id[x]), org = to2[tmp];
            if (from[tmp] == x)
                from[tmp] = to2[tmp] = 0;
            else
            {
                to2[tmp] = toSameDepth(from[tmp], x);
                SegTree::add(1, 1, n, id[to2[tmp]], id[to2[tmp]] + sz[to2[tmp]] - 1, 1);
            }
            upd(x, org, last);
            x = fa[org];
            last = org;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(head, -1, sizeof(head));
    cin >> n >> m;
    totColor = n;
    for (int i = 1, u, v; i < n; i++)
    {
        cin >> u >> v;
        link(u, v);
        link(v, u);
    }
    HLD::dfs1(1, 0, 1);
    HLD::dfs2(1, 1);
    SegTree::build(1, 1, n);
    while (m--)
    {
        int op, x, y;
        cin >> op;
        switch (op)
        {
        case 1:
            cin >> x;
            HLD::update(x);
            break;
        case 2:
            cin >> x >> y;
            cout << HLD::rangeSum(x, y) << '\n';
            break;
        default:
            cin >> x;
            cout << HLD::treeMax(x) << '\n';
        }
    }
    return 0;
}