[SDOI 2017]ツリーポイント塗装(LCT、ツリーチェーン断面、線分ツリー)

Description
木を与える
パスを定義する権利は、このパスの点(始点と終点を含む)はいくつの色がありますか?
3つの操作をサポートすることを要求します.

x,点xをルートノードの経路上のすべての点に、使用したことのない新しい色に染めます.

x,y x,y,xからyまでの経路の権利を求める.

x xは、xを根とするサブツリーの中で、ルートノードへの経路の権利値が最大となるように、1つの点を選択し、最大の重みを求める.

Solution
1を操作すると、LCT L C Tのaccess a c e sと似ていて、重いチェーンの一部を色として見ることができます.したがって、access a c c e sで動作する場合は、元の息子の子樹＋1＋1、現在の息子の子樹−1−1となります.チェーンを使って+線分の木を切り開いて維持します.
操作2の答えはf(x)＋f(y)−f(l c a)＋f(x)＋f(y)−f(l c)−2＋1であり、fは経路(u,root)(u,r o o t)の権利値である.
操作3の答えはx子樹の中の最大値です.

#include 
using namespace std;

const int maxn = 100005;
int n, m, dfn[maxn], low[maxn], Time;

inline int gi()
{
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    int sum = 0;
    while ('0' <= c && c <= '9') sum = sum * 10 + c - 48, c = getchar();
    return sum;
}

#define mid ((l + r) >> 1)
#define lch (s << 1)
#define rch (s << 1 | 1)

int lazy[maxn * 4], Max[maxn * 4];

inline void pushdown(int s)
{
    lazy[lch] += lazy[s]; Max[lch] += lazy[s];
    lazy[rch] += lazy[s]; Max[rch] += lazy[s];
    lazy[s] = 0;
}

void modify(int s, int l, int r, int x, int y, int val)
{
    if (x <= l && r <= y) {
        lazy[s] += val; Max[s] += val;
        return;
    }
    pushdown(s);
    if (x <= mid) modify(lch, l, mid, x, y, val);
    if (y >= mid + 1) modify(rch, mid + 1, r, x, y, val);
    Max[s] = max(Max[lch], Max[rch]);
}

int query(int s, int l, int r, int x, int y)
{
    if (x <= l && r <= y) return Max[s];
    pushdown(s);
    int ret = 0;
    if (x <= mid) ret = max(ret, query(lch, l, mid, x, y));
    if (y >= mid + 1) ret = max(ret, query(rch, mid + 1, r, x, y));
    return ret;
}

#define get(x) (ch[f[x]][1] == x)
#define isroot(x) (ch[f[x]][0] != x && ch[f[x]][1] != x)

int f[maxn], ch[maxn][2];

inline void rotate(int x)
{
    int fa = f[x], gfa = f[fa], k = get(x);
    if (!isroot(fa)) ch[gfa][get(fa)] = x;
    ch[fa][k] = ch[x][k ^ 1]; f[ch[x][k ^ 1]] = fa;
    ch[x][k ^ 1] = fa; f[fa] = x;
    f[x] = gfa;
}

inline void splay(int x)
{
    while (!isroot(x)) {
        int fa = f[x];
        if (!isroot(fa))
            get(x) ^ get(fa) ? rotate(x) : rotate(fa);
        rotate(x);
    }
}

inline int findroot(int x)
{
    while (ch[x][0]) x = ch[x][0];
    return x;
}

inline void access(int x)
{
    for (int y = 0, u; x; y = x, x = f[x]) {
        splay(x);
        if (ch[x][1])
            u = findroot(ch[x][1]),
            modify(1, 1, n, dfn[u], low[u], 1);
        ch[x][1] = y;
        if (ch[x][1])
            u = findroot(ch[x][1]),
            modify(1, 1, n, dfn[u], low[u], -1);
    }
}

struct edge {
    int to, next;
}e[maxn * 2];
int h[maxn], tot;

inline void add(int u, int v)
{
    e[++tot] = (edge) {v, h[u]}; h[u] = tot;
    e[++tot] = (edge) {u, h[v]}; h[v] = tot;
}

int son[maxn], siz[maxn], g[maxn], F[maxn], dep[maxn];
void dfs1(int u, int fa)
{
    f[u] = F[u] = fa; dfn[u] = ++Time; siz[u] = 1;
    dep[u] = dep[fa] + 1;
    for (int i = h[u], v; v = e[i].to, i; i = e[i].next)
        if (v != fa) {
            dfs1(v, u); siz[u] += siz[v];
            if (siz[son[u]] < siz[v]) son[u] = v;
        }
    low[u] = Time;
}

void dfs2(int u, int fa)
{
    if (son[u]) g[son[u]] = g[u], dfs2(son[u], u);
    for (int i = h[u], v; v = e[i].to, i; i = e[i].next)
        if (v != son[u] && v != fa) 
            g[v] = v, dfs2(v, u);
}

int lca(int u, int v)
{
    while (g[u] != g[v]) {
        if (dep[g[u]] < dep[g[v]]) v = F[g[v]];
        else u = F[g[u]];
    }
    return dep[u] < dep[v] ? u : v;
}

int main()
{
    n = gi(); m = gi();
    for (int u, v, i = 1; i < n; ++i) {
        u = gi(); v = gi(); add(u, v);
    }

    dfs1(1, 0);
    g[1] = 1; dfs2(1, 0);

    for (int i = 1; i <= n; ++i)
        modify(1, 1, n, dfn[i], dfn[i], dep[i]);

    int opt, x, y, z, cnt = 0;
    while (m--) {
        opt = gi();
        if (opt > 1) ++cnt;
        if (opt == 1) x = gi(), access(x);
        else if (opt == 2) {
            x = gi(); y = gi(); z = lca(x, y);
            printf("%d
", query(1, 1, n, dfn[x], dfn[x]) + query(1, 1, n, dfn[y], dfn[y]) - query(1, 1, n, dfn[z], dfn[z]) * 2 + 1);
        }
        else if (opt == 3) {
            x = gi();
            printf("%d
", query(1, 1, n, dfn[x], low[x]));
        }
    }

    return 0;
}