LYDSY 4538

题目大意

暂无

题目解法

暂无

RTFC

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <queue>
inline void read(int &x)
{
    int ch = x = 0, flag = 1;
    while (!isdigit(ch = getchar()))
        if (ch == '-') flag = -1;
    for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    x *= flag;
}
const int inf = 0x3f3f3f3f, N = int(1e5 + 5), M = N << 1;
#define avg(x, y) ((x) + (((y) - (x)) >> 1))
#define L(x) ((x) << 1)
#define R(x) ((x) << 1 | 1)
template <typename T>
struct __ext_priority_queue
{
private:
    std::priority_queue<T> a, b;

public:
    void push(const T &x) { a.push(x); }
    void pop(const T &x) { b.push(x); }
    T top()
    {
        while (!b.empty() && a.top() == b.top()) a.pop(), b.pop();
        return a.empty() ? -1 : a.top();
    }
};
__ext_priority_queue<int> node[N << 2];
void modify(int k, int l, int r, int x, int y, int v, bool t)
{
    if (x <= l && r <= y) return void(t ? node[k].push(v) : node[k].pop(v));
    int m = avg(l, r);
    if (x < m) modify(L(k), l, m, x, y, v, t);
    if (y > m) modify(R(k), m, r, x, y, v, t);
}
int query(int k, int l, int r, int p)
{
    int cur = node[k].top();
    if (l == r - 1) return cur;
    int m = avg(l, r);
    return std::max(cur, p < m ? query(L(k), l, m, p) : query(R(k), m, r, p));
}
int adj[N], nxt[N << 1], to[N << 1], ecnt;
inline void addEdge(int f, int t)
{
    ecnt++;
    nxt[ecnt] = adj[f];
    adj[f] = ecnt;
    to[ecnt] = t;
}
int n, m;
int sz[N], fa[N], dep[N], son[N], top[N], idx[N], pos[N];
void HLD()
{
    int u, v, len = 0;
    static int que[N];
    que[len++] = 1;
    for (int i = 0; i < len; i++)
    {
        sz[u = que[i]] = 1;
        for (int e = adj[u]; e; e = nxt[e])
            if ((v = to[e]) != fa[u])
                fa[v] = u, dep[v] = dep[u] + 1, que[len++] = v;
    }
    for (int i = len - 1; i; i--)
    {
        u = que[i], v = fa[u];
        sz[v] += sz[u];
        if (sz[u] > sz[son[v]]) son[v] = u;
    }
    for (int i = 0, tot = 0; i < len; i++)
        if (top[u = que[i]] == 0)
            for (v = u; v; v = son[v])
                top[idx[pos[v] = tot++] = v] = u;
}
void work(int u, int v, int w, bool t)
{
    typedef std::pair<int, int> seg;
    static seg segs[N];
    int scnt = 0;
    segs[scnt++] = seg(-1, -1);
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
        segs[scnt++] = seg(pos[top[u]], pos[u]);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) std::swap(u, v);
    segs[scnt++] = seg(pos[u], pos[v]);
    segs[scnt] = seg(n, n);
    std::sort(segs, segs + scnt);
    for (int i = 0; i <= scnt; i++)
        if (segs[i].second + 1 < segs[i + 1].first)
            modify(1, 0, n, segs[i].second + 1, segs[i + 1].first, w, t);
}
int main()
{
    read(n), read(m);
    for (int i = 1, u, v; i < n; i++) read(u), read(v), addEdge(u, v), addEdge(v, u);
    HLD();
    for (int i = 1; i <= m; i++)
    {
        static int Qf[M], Qt[M], Qv[M];
        int type;
        read(type);
        if (type == 0)
        {
            read(Qf[i]), read(Qt[i]), read(Qv[i]);
            work(Qf[i], Qt[i], Qv[i], true);
        }
        if (type == 1)
        {
            int t;
            read(t);
            work(Qf[t], Qt[t], Qv[t], false);
        }
        if (type == 2)
        {
            int x;
            read(x);
            printf("%d\n", query(1, 0, n, pos[x]));
        }
    }
    return 0;
}