题意:
给一棵树,每个点都有点权,然后m个询问,要求u节点到v节点这条路径上第k小的点权,强制在线。
题解:
树上建主席树,查询即为树上差分:sum[v]+sum[u]-sum[lca(u,v)]-sum[fa[lca(u,v)]]
非强制在线版本:https://www.spoj.com/problems/COT/
参考代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 5;
int n, m, cnt;
int a[MAXN + 10], b[MAXN + 10];
struct EDGE
{
int v, nxt;
} edge[(MAXN + 10) << 1];
int ecnt = 0, fir[MAXN];
void addedge(int u, int v)
{
edge[ecnt].v = v;
edge[ecnt].nxt = fir[u];
fir[u] = ecnt++;
}
int tot = 0;
int Tree[MAXN + 10], sum[(MAXN + 10) << 6], ls[(MAXN + 10) << 6], rs[(MAXN + 10) << 6];
void update(int las, int val, int l, int r, int &rt)
{
rt = ++tot;
ls[rt] = ls[las];
rs[rt] = rs[las];
sum[rt] = sum[las] + 1;
if (l == r)
return;
int mid = (l + r) >> 1;
if (val <= mid)
update(ls[las], val, l, mid, ls[rt]);
else
update(rs[las], val, mid + 1, r, rs[rt]);
}
int query(int u, int v, int lca, int f_lca, int l, int r, int k)
{
int tmp = sum[ls[u]] + sum[ls[v]] - sum[ls[lca]] - sum[ls[f_lca]];
int mid = (l + r) >> 1;
if (l >= r)
return b[l];
if (k <= tmp)
return query(ls[u], ls[v], ls[lca], ls[f_lca], l, mid, k);
else
return query(rs[u], rs[v], rs[lca], rs[f_lca], mid + 1, r, k - tmp);
}
int grand[MAXN + 10][25], depth[MAXN + 10];
void dfs_lca(int u, int FA, int dep)
{
depth[u] = dep;
grand[u][0] = FA;
for (int i = 1; (1 << i) <= dep; i++)
grand[u][i] = grand[grand[u][i - 1]][i - 1];
for (int i = fir[u]; i != -1; i = edge[i].nxt)
{
int v = edge[i].v;
if (v == FA)
continue;
update(Tree[u], a[v], 1, n, Tree[v]);
dfs_lca(v, u, dep + 1);
}
}
int LCA(int x, int y)
{
if (x == y)
return x;
if (depth[x] > depth[y])
swap(x, y);
for (int i = 20; i >= 0; i--)
if (depth[x] < depth[y] && depth[x] <= depth[grand[y][i]])
y = grand[y][i];
if (x == y)
return x;
for (int i = 20; i >= 0; i--)
if (grand[x][i] != grand[y][i])
x = grand[x][i], y = grand[y][i];
if (grand[x][0] == 0 && grand[y][0] == 0 && x != y)
return -1;
return grand[x][0];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]), b[i] = a[i];
sort(b + 1, b + 1 + n);
cnt = unique(b + 1, b + 1 + n) - (b + 1);
for (int i = 1; i <= n; i++)
a[i] = lower_bound(b + 1, b + 1 + cnt, a[i]) - b;
ecnt = 0;
memset(fir, -1, sizeof(fir));
for (int i = 1; i <= n - 1; i++)
{
int u, v;
scanf("%d%d", &u, &v);
addedge(u, v);
addedge(v, u);
}
update(Tree[0], a[1], 1, n, Tree[1]);
dfs_lca(1, 0, 1);
int ans = 0;
while (m--)
{
int u, v, k;
scanf("%d%d%d", &u, &v, &k);
u ^= ans;
int lca = LCA(u, v);
ans = query(Tree[u], Tree[v], Tree[lca], Tree[grand[lca][0]], 1, n, k);
printf("%d\n", ans);
}
return 0;
}