【题解】HNOI2016网络

　　整体二分是个好东西！可我忘记了它QAQ其实当你知道这题可以整体二分的时候就已经不难了（个人觉得这是最难想到的一点啊）。整体二分的话，我们就可以把问题转化为是否有一条权值 \(>= k\) 的链经过某一点，这个可以通过树上差分做到 \(logn\) 的复杂度。而由于每次二分答案之后，都可以将询问和操作分成两个部分，所以是满足整体二分的性质的。

　　以及自己的代码能力还有待提升啊……(；д；)

#include <bits/stdc++.h>

using namespace std;

#define lowbit(i) (i & (-i))

#define maxn 1000000

#define INF 99999999

#define CNST 20

int n, m, tot, book[maxn];

int b[maxn], id[maxn];

int C[maxn], Ans[maxn], pos[maxn];

int dfn[maxn], size[maxn], f[maxn];

int timer, cnt, ST[maxn * ][CNST];

int bit[CNST], Log[maxn * ];

map <int, int> Map;

int read()

{

    int x = , k = ;

    char c; c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

struct node

{

    int opt, x, y, w, mark, id, rec;

}Q[maxn], ql[maxn], qr[maxn];

struct edge

{

    int cnp, to[maxn], last[maxn], head[maxn];

    edge() { cnp = ; }

    void add(int u, int v)

    {

        to[cnp] = v, last[cnp] = head[u], head[u] = cnp ++;

        to[cnp] = u, last[cnp] = head[v], head[v] = cnp ++;

    }

}E1;

void Update(int x, int y)

{

    if(!x) return;

    for(; x <= n; x += lowbit(x)) C[x] += y;

}

int Query(int x)

{

    int ret = ;

    for(; x; x -= lowbit(x)) ret += C[x];

    return ret;

}

void dfs(int u, int fa)

{

    dfn[u] = ++ timer; size[u] = ; f[dfn[u]] = dfn[fa];

    ST[++ cnt][] = dfn[u]; pos[u] = cnt;

    for(int i = E1.head[u]; i; i = E1.last[i])

    {

        int v = E1.to[i];

        if(v == fa) continue;

        dfs(v, u); size[u] += size[v];

        ST[++ cnt][] = dfn[u];

    }

}

int RMQ(int u, int v)

{

    u = pos[u], v = pos[v];

    if(u > v) swap(u, v);

    int k = Log[v - u + ];

    return min(ST[u][k], ST[v - bit[k] + ][k]);

}

void Check(int l, int r, int ll, int rr)

{

    if(l == r)

    {

        for(int i = ll; i <= rr; i ++)

            if(Q[i].opt == )

                Ans[Q[i].id] = l ? id[l] : -;

        return;

    }

    if(l > r) return;

    int mid = (l + r) >> , sum = ;

    for(int i = ll; i <= rr; i ++)

    {

        int x = Q[i].x, y = Q[i].y;

        if(!Q[i].opt && Q[i].rec > mid)

        {

            Update(dfn[x], ), Update(dfn[y], );

            int K = RMQ(x, y);

            Update(K, -), Update(f[K], -); sum ++;

        }

        else if(Q[i].opt ==  && Q[i].rec > mid)

        {

            Update(dfn[x], -), Update(dfn[y], -);

            int K = RMQ(x, y);

            Update(K, ), Update(f[K], ); sum --;

        }

        else if(Q[i].opt == )

        {

            int x = Query(dfn[Q[i].x] + size[Q[i].x] - ) - Query(dfn[Q[i].x] - );

            if(x < sum) Q[i].mark = ;

        }

    }

    for(int i = ll; i <= rr; i ++)

    {

        int x = Q[i].x, y = Q[i].y;

        if(!Q[i].opt && Q[i].rec > mid && !book[Q[i].id])

        {

            Update(dfn[x], -), Update(dfn[y], -);

            int K = RMQ(x, y);

            Update(K, ), Update(f[K], );

        }

    }

    int L = , R = ;

    for(int i = ll; i <= rr; i ++)

    {

        if(Q[i].opt == )

        {

            if(Q[i].mark) Q[i].mark = , qr[++ R] = Q[i];

            else ql[++ L] = Q[i];

        }

        else if(Q[i].rec > mid) qr[++ R] = Q[i];

        else ql[++ L] = Q[i];

    }

    int rec = ll - , ls = , rs = ;

    while(ls <= L) Q[++ rec] = ql[ls], ls ++;

    while(rs <= R) Q[++ rec] = qr[rs], rs ++;

    Check(l, mid, ll, ll + ls - );

    Check(mid + , r, ll + ls - , rr);

}

void init()

{

    bit[] = ; for(int i = ; i < CNST; i ++) bit[i] = bit[i - ] << ;

    Log[] = -; for(int i = ; i < maxn * ; i ++) Log[i] = Log[i >> ] + ;

}

int main()

{

    init();

    n = read(), m = read();

    for(int i = ; i <= m; i ++) Ans[i] = -INF;

    for(int i = ; i < n; i ++)

    {

        int u = read(), v = read();

        E1.add(u, v);

    }

    dfs(, );

    for(int i = ; i <= Log[cnt]; i ++)

        for(int j = ; j + bit[i - ] <= cnt; j ++)

            ST[j][i] = min(ST[j][i - ], ST[j + bit[i - ]][i - ]);

    for(int i = ; i <= m; i ++)

    {

        Q[i].opt = read(); Q[i].id = i;

        if(Q[i].opt == )

        {

            Q[i].x = read(), Q[i].y = read(), Q[i].w = read();

            b[++ tot] = Q[i].w;

        }

        else if(Q[i].opt == )

        {

            int t = read(); book[t] = ;

            Q[i] = Q[t], Q[i].opt = ;  Q[i].id = i;

        }

        else if(Q[i].opt == ) Q[i].x = read();

    }

    sort(b + , b +  + tot); int tem = ;

    for(int i = ; i <= tot; i ++)

        if(b[i] != b[i - ]) Map[b[i]] = ++ tem, id[tem] = b[i];

    tot = tem;

    for(int i = ; i <= m; i ++)

        if(!Q[i].opt || Q[i].opt == ) Q[i].rec = Map[Q[i].w];

    Check(, tot, , m);

    for(int i = ; i <= m; i ++)

        if(Ans[i] != -INF) printf("%d\n", Ans[i]);

    return ;

}