SPOJ QTREE_HLD

题目大意

暂无

题目解法

暂无

RTFC

#include <cctype>
#include <cstdio>
#include <cstring>
#define L(x) ((x) << 1)
#define R(x) ((x) << 1 | 1)
#define avg(x, y) (((x) + (y)) >> 1)
const int N = 20005, M = N << 1, inf = 0x3f3f3f3f;
template <typename T>
inline void swap(T &x, T &y)
{
    T t = x;
    x = y;
    y = t;
}
template <typename T>
inline T max(const T &x, const T &y) { return x > y ? x : y; }
int U[N], V[N], W[N], adj[N], nxt[M], to[M], val[N], ecnt, mx[N << 2];
int sz[N], son[N], dep[N], top[N], fa[N], pos[N], idx[N];
inline void addEdge(int f, int t)
{
    ecnt++;
    nxt[ecnt] = adj[f];
    adj[f] = ecnt;
    to[ecnt] = t;
}
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;
}
void build(int k, int l, int r)
{
    if (l == r - 1) return void(mx[k] = val[idx[l]]);
    int m = avg(l, r);
    build(L(k), l, m);
    build(R(k), m, r);
    mx[k] = max(mx[L(k)], mx[R(k)]);
}
void modify(int k, int l, int r, int p, int v)
{
    if (l == r - 1) return void(mx[k] = v);
    int m = avg(l, r);
    (p < m) ? modify(L(k), l, m, p, v) : modify(R(k), m, r, p, v);
    mx[k] = max(mx[L(k)], mx[R(k)]);
}
int qmax(int k, int l, int r, int x, int y)
{
    if (x <= l && r <= y) return mx[k];
    int m = avg(l, r), res = -inf;
    if (x < m) res = max(res, qmax(L(k), l, m, x, y));
    if (y > m) res = max(res, qmax(R(k), m, r, x, y));
    return res;
}
int n;
int pmax(int x, int y)
{
    int res = -inf;
    while (top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        res = max(res, qmax(1, 0, n, pos[top[x]], pos[x] + 1));
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    return max(res, qmax(1, 0, n, pos[x] + 1, pos[y] + 1));
}
int main()
{
    static int que[N];
    int T;
    read(T);
    while (T--)
    {
        ecnt = 0;
        memset(adj, 0, sizeof(adj));
        memset(son, 0, sizeof(son));
        memset(top, 0, sizeof(top));
        read(n);
        for (int i = 1; i < n; i++) read(U[i]), read(V[i]), read(W[i]), addEdge(U[i], V[i]), addEdge(V[i], U[i]);
        int len = 0, u, v;
        val[que[len++] = 1] = -inf;
        for (int i = 0; i < len; i++)
            for (int e = adj[u = que[i]]; e; e = nxt[e])
                if ((v = to[e]) != fa[u])
                    fa[v] = u, dep[v] = dep[u] + 1, que[len++] = v;
        for (int i = 1; i < n; ++i) val[dep[U[i]] > dep[V[i]] ? U[i] : V[i]] = W[i];
        for (int i = 0; i < len; i++) sz[que[i]] = 1;
        for (int i = len - 1; i > 0; 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 < n; i++)
            if (top[u = que[i]] == 0)
                for (v = u; v; v = son[v])
                    idx[pos[v] = tot++] = v, top[v] = u;
        build(1, 0, n);
        char op[10];
        while (true)
        {
            scanf("%s", op);
            if (*op == 'D') break;
            read(u), read(v);
            if (*op == 'C') modify(1, 0, n, pos[dep[U[u]] > dep[V[u]] ? U[u] : V[u]], v);
            if (*op == 'Q') printf("%d\n", pmax(u, v));
        }
    }
    return 0;
}