Pishty and Tree

题目描述

A little boy Pishty lives in Khust - an ancient town in Uzhlyandia with their medieval castles and smart bears.

The gem of Khust is a very valuable castle because it protects the citizens of Uhzlyandia from the Durdom kingdom’s army. Pishty also like this castle because it hides old secrets in long halls and high towers…

The castle can be described as an undirected tree with $N$ vertices and $N-1$ edges. Each edge has a magic number $C$.

When a group of tourists visit the castle, they are interested in a path between vertices $U$ and $V$. They think that an edge is interesting if its magic number is less than or equal to $K$. The total attractivity of the path is the xor of all interesting edges on it.

The emperor of Uzhlyandia is interested in tourism development, and so he wants to find the total attractivity of the paths for each group. Because Pishty wants to become the emperor’s knight, he wants to know all of this information too. But he can’t do it on his own because there are a large number of groups. Please help Pishty to solve this unthinkable problem.

Given $M$ groups of tourists, find the total attractivity of the path for each group.

题意概述

给定一棵有$N$个节点的树，每条边都有一个权值$C$。有$M$组询问，每组询问给定$U, V$和$K$，求$U$到$V$路径上权值不超过$K$的边的权值的异或和。

数据范围：$1 \le N, M \le 10^5, \ 1 \le C, K \le 10^9$。

算法分析 1

由于要求的是异或和，且$x \oplus y \oplus y=x$，因此可以分别求出$U, V$到根节点路径上权值不超过$K$的边的权值的异或和，将两个结果异或一下便得到了答案。

考虑采用树链剖分。定义重边为一个节点连向它最大子树的边，由重边构成的链称为重链；其他边均为轻边。令$size_x$表示以节点$x$为根的子树大小。对于一条轻边$(u, v)$，有$2size_v \lt size_u$。对于树中的任一节点，从根节点到它的路径上不超过$O(\log n)$条重链，不超过$O(\log n)$条轻边。在重链上用树状数组维护前缀和，即可在$O(\log^2n)$的时间内给出一组询问的答案。

因为有$K$这个限制，所以我们考虑离线做法：将边按$C$从小到大排序，将询问按$K$从小到大排序，在加入边的同时处理询问。

代码 1

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
struct edge {
  long long u, v, c, nxt;
  bool operator < (const edge &a) const { return c < a.c; }
} e[200001], r[100001];
struct ask {
  long long u, v, k, id, ans;
  bool operator < (const ask &a) const { return k < a.k; }
} a[100001];
bool cmp(ask a, ask b) { return a.id < b.id; }
struct binary_indexed_tree {
  long long n;
  vector<long long> a;
  void init(long long t) { n = t + 10, a.clear(), a.resize(n); }
  void add(long long p, long long t) {
    for (long long i = p; i < n; i += i & -i) a[i] ^= t;
  }
  long long sum(long long p) {
    long long ret = 0;
    for (long long i = p; i; i -= i & -i) ret ^= a[i];
    return ret;
  }
} tree[100001];
long long T, n, m, nume, tot, pnt, h[100001], size[100001];
long long up[100001], down[100001], father[100001], dist[100001];
long long id[100001], len[100001], cnt[100001];
void add_edge(long long u, long long v, long long c) {
  e[++nume].u = u, e[nume].v = v, e[nume].c = c;
  e[nume].nxt = h[u], h[u] = nume;
  e[++nume].u = v, e[nume].v = u, e[nume].c = c;
  e[nume].nxt = h[v], h[v] = nume;
}
void dfs(long long t, long long fa, long long depth) {
  long long ma = 0;
  size[t] = 1, father[t] = fa, dist[t] = depth;
  for (long long i = h[t]; i; i = e[i].nxt) {
    if (e[i].v != fa) {
      dfs(e[i].v, t, e[i].c);
      ma = max(ma, size[e[i].v]);
      size[t] += size[e[i].v];
    }
  }
  for (long long i = h[t]; i; i = e[i].nxt) {
    if (e[i].v != fa && ma == size[e[i].v]) { down[t] = e[i].v; break; }
  }
}
void init(long long t, long long fa, long long rt) {
  if (!up[t]) id[up[t] = t] = ++tot, ++cnt[t], len[t] = 1;
  else ++cnt[up[t] = rt], len[t] = len[fa] + 1;
  for (long long i = h[t]; i; i = e[i].nxt) {
    if (e[i].v != fa) {
      if (!up[e[i].v]) init(e[i].v, t, e[i].v);
      else init(e[i].v, t, rt);
    }
  }
  if (t == up[t]) tree[id[t]].init(cnt[t]);
}
void insert_line(edge e) {
  if (up[e.u] == up[e.v] && len[e.u] < len[e.v]) {
    tree[id[up[e.u]]].add(len[e.u], e.c);
  }
}
long long query(long long u, long long k) {
  long long ret = 0;
  while (u != 1) {
    ret ^= tree[id[up[u]]].sum(len[u] - 1);
    u = up[u];
    if (u != 1) {
      if (dist[u] <= k) ret ^= dist[u];
      u = father[u];
    }
  }
  return ret;
}
int main()
{
  scanf("%lld", &T);
  while (T--) {
    scanf("%lld", &n);
    nume = tot = 0, pnt = 1;
    memset(h, 0, sizeof(h));
    memset(up, 0, sizeof(up));
    memset(down, 0, sizeof(down));
    memset(cnt, 0, sizeof(cnt));
    for (long long i = 1; i < n; ++i) {
      r[i].nxt = 0;
      scanf("%lld%lld%lld", &r[i].u, &r[i].v, &r[i].c);
    }
    sort(r + 1, r + n);
    for (long long i = 1; i < n; ++i) add_edge(r[i].u, r[i].v, r[i].c);
    dfs(1, 0, 0);
    for (long long i = 1; i <= n; ++i) if (down[i]) up[down[i]] = i;
    init(1, 0, 1);
    scanf("%lld", &m);
    for (long long i = 1; i <= m; ++i) {
      a[i].id = i, a[i].ans = 0;
      scanf("%lld%lld%lld", &a[i].u, &a[i].v, &a[i].k);
    }
    sort(a + 1, a + m + 1);
    for (long long i = 1; i <= m; ++i) {
      while (pnt <= nume && e[pnt].c <= a[i].k) insert_line(e[pnt++]);
      a[i].ans = query(a[i].u, a[i].k) ^ query(a[i].v, a[i].k);
    }
    sort(a + 1, a + m + 1, cmp);
    for (long long i = 1; i <= m; ++i) printf("%lld\n", a[i].ans);
  }
  return 0;
}

算法分析 2

由于要求的是异或和，因此可以对整棵树建可持久化 Trie 树，每次询问直接查询$U, V$到根节点的路径上边权不超过$K$的边的权值的异或和，将两结果异或起来。

代码 2

#include <cstdio>
#include <cstring>
using namespace std;
struct node_type {
  long long val, child[2];
} node[4000001];
struct edge {
  long long v, c, nxt;
} e[200001];
long long T, n, m, tot, nume, h[100001], root[100001];
void add_edge(long long u, long long v, long long c) {
  e[++nume].v = v, e[nume].c = c, e[nume].nxt = h[u], h[u] = nume;
  e[++nume].v = u, e[nume].c = c, e[nume].nxt = h[v], h[v] = nume;
}
long long insert_node(long long root, long long val, long long depth) {
  if (depth < 0) {
    node[++tot].val = node[root].val ^ val, node[tot].child[0] = node[tot].child[1] = 0;
    return tot;
  }
  long long t = (val >> depth) & 1;
  long long ch = insert_node(node[root].child[t], val, depth - 1);
  node[++tot].child[t] = ch, node[tot].child[!t] = node[root].child[!t];
  node[tot].val = node[node[tot].child[t]].val ^ node[node[tot].child[!t]].val;
  return tot;
}
void dfs(long long t, long long fa) {
  for (int i = h[t]; i; i = e[i].nxt) {
    if (e[i].v != fa) {
      root[e[i].v] = insert_node(root[t], e[i].c, 30);
      dfs(e[i].v, t);
    }
  }
}
long long get_dist(long long root, long long k, long long depth) {
  if (depth < 0) return node[root].val;
  long long t = (k >> depth) & 1;
  if (t) return node[node[root].child[0]].val ^ get_dist(node[root].child[1], k, depth - 1);
  else return get_dist(node[root].child[0], k, depth - 1);
}
int main()
{
  scanf("%lld", &T);
  while (T--) {
    scanf("%lld", &n);
    nume = tot = 0;
    memset(h, 0, sizeof(h));
    for (int i = 1; i < n; ++i) {
      long long u, v, c;
      scanf("%lld%lld%lld", &u, &v, &c);
      add_edge(u, v, c);
    }
    root[1] = insert_node(0, 0, 30);
    dfs(1, 0);
    scanf("%lld", &m);
    for (int i = 1; i <= m; ++i) {
      long long u, v, k;
      scanf("%lld%lld%lld", &u, &v, &k);
      printf("%lld\n", get_dist(root[u], k, 30) ^ get_dist(root[v], k, 30));
    }
  }
  return 0;
}