SPOJ COT

题目大意

暂无

题目解法

暂无

RTFC

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#define avg(x, y) (x + ((y - x) >> 1))
inline void read(int &x)
{
    int ch = x = 0, sign = 1;
    while (!isdigit(ch = getchar()))
        if (ch == '-') sign = -1;
    for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    x *= sign;
}
const int N = 400010;
int W[N], adj[N], to[N << 1], nxt[N << 1], ecnt;
int fa[N], dep[N], root[N], rcnt;
inline void addEdge(int f, int t)
{
    ecnt++;
    nxt[ecnt] = adj[f];
    adj[f] = ecnt;
    to[ecnt] = t;
}
int n;
struct node
{
    int l, r, v;
} t[N << 5];
void insert(int p, int &x, int l, int r, int v)
{
    (t[x = ++rcnt] = t[p]).v++;
    if (l == r - 1) return;
    int m = avg(l, r);
    v < m ? insert(t[p].l, t[x].l, l, m, v) : insert(t[p].r, t[x].r, m, r, v);
}
int query(int a, int b, int c, int d, int k)
{
    int l = 0, r = n;
    while (l != r - 1)
    {
        int mid = avg(l, r);
        if (t[t[a].l].v + t[t[b].l].v - t[t[c].l].v - t[t[d].l].v >= k)
        {
            a = t[a].l, b = t[b].l, c = t[c].l, d = t[d].l;
            r = mid;
        }
        else
        {
            k -= t[t[a].l].v + t[t[b].l].v - t[t[c].l].v - t[t[d].l].v;
            a = t[a].r, b = t[b].r, c = t[c].r, d = t[d].r;
            l = mid;
        }
    }
    return l;
}
int F[N][20];
void init_lca()
{
    for (int i = 1; i <= n; i++) F[i][0] = fa[i];
    for (int j = 1; j < 20; j++)
        for (int i = 1; i <= n; i++)
            F[i][j] = F[F[i][j - 1]][j - 1];
}
int LCA(int x, int y)
{
    if (dep[x] < dep[y]) std::swap(x, y);
    for (int i = 19; i >= 0; --i)
        if (dep[F[x][i]] >= dep[y])
            x = F[x][i];
    if (x == y) return x;
    for (int i = 19; i >= 0; --i)
        if (F[x][i] != F[y][i])
            x = F[x][i], y = F[y][i];
    return fa[x];
}
int main()
{
    int m;
    read(n), read(m);
    for (int i = 1; i <= n; i++) read(W[i]);
    static int H[N];
    memcpy(H, W + 1, n << 4);
    std::sort(H, H + n);
    int tend = int(std::unique(H, H + n) - H);
    for (int i = 1; i <= n; i++) W[i] = int(std::lower_bound(H, H + tend, W[i]) - H);
    for (int i = 1, u, v; i < n; i++)
        read(u), read(v), addEdge(u, v), addEdge(v, u);
    static int que[N];
    int len = 0;
    que[len++] = 1;
    for (int i = 0; i < len; i++)
    {
        int x = que[i];
        dep[x] = dep[fa[x]] + 1;
        insert(root[fa[x]], root[x], 0, n, W[x]);
        for (int e = adj[x]; e; e = nxt[e])
            if (to[e] != fa[x])
                fa[que[len++] = to[e]] = x;
    }
    init_lca();
    for (int i = 0, u, v, k, ans = 0; i < m; i++)
    {
        read(u), read(v), read(k);
        ans = H[query(root[u], root[v], root[LCA(u, v)], root[fa[LCA(u, v)]], k)];
        printf("%d", ans);
        if (i != m - 1) putchar('\n');
    }
    return 0;
}