Hide

题意概述

有一棵$N$个节点的树,每个节点都是黑色或白色。有$Q$次操作,动态修改点的颜色,询问最远黑点对之间的距离。
数据范围:$1 \le N \le 10^5, \; 1 \le Q \le 5 \times 10^5$。

算法分析

考虑点分治,构造一棵重心树。为了方便,下面所有距离均表示在原树上的距离,堆均为大根堆。
设节点$i$在重心树上的父亲为$p_i$。对于每个节点$u$维护两个堆,第一个堆用来维护重心树上$u$子树中的所有黑点到$p_u$的距离,第二个堆用来维护重心树上$u$各个子树中距离$u$最远的黑点到$u$的距离。那么第二个堆可以借助第一个堆来维护。
接着需要一个全局的堆,用来维护所有节点第二个堆的前两个元素之和(经过该点的路径)以及所有黑点第二个堆的第一个元素(以该点为端点的路径)。
修改时,沿着重心树往上依次处理经过的节点,先在全局的堆中删除,再在第二个堆中删除,在第一个堆中修改后,维护第二个堆和全局的堆。

代码

/*
 * Computer programmers do it byte by byte.
 */

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

template <typename T> void read(T &n) {
  char c;
  for (; (c = getchar()) < '0' || c > '9';)
    ;
  for (n = c - '0'; (c = getchar()) >= '0' && c <= '9'; (n *= 10) += c - '0')
    ;
}

typedef int const ic;

static ic N = 100005;

class heap {
private:
  std::priority_queue<int> que, buf;

void clear() {
    for (; !que.empty() && !buf.empty() && que.top() == buf.top();
         que.pop(), buf.pop())
      ;
  }

public:
  void push(ic &n) {
    if (n)
      que.push(n);
  }

void erase(ic &n) {
    if (n)
      buf.push(n);
  }

void pop() {
    clear();
    if (!que.empty())
      que.pop();
  }

int top() {
    clear();
    return que.empty() ? 0 : que.top();
  }

int top2() {
    clear();
    if (que.empty())
      return 0;
    int tmp = que.top(), ret = tmp;
    que.pop(), clear();
    if (que.empty()) {
      que.push(tmp);
      return 0;
    }
    ret += que.top(), que.push(tmp);
    return ret;
  }
} global;

namespace tree {
int n, nume, h[N], col[N];
int tim, fi[N], dep[N], lca[N << 1][20];
int power[N << 1];
int root, up[N], size[N], mx[N], vis[N];
heap toup[N], me[N];
struct Edge {
  int v, nxt;
} e[N << 1];

void add_edge(ic &u, ic &v) {
  e[++nume] = (Edge){v, h[u]}, h[u] = nume;
  e[++nume] = (Edge){u, h[v]}, h[v] = nume;
}

void dfs(ic &t, ic &fa) {
  lca[++tim][0] = t, fi[t] = tim, dep[t] = dep[fa] + 1;
  for (int i = h[t]; i; i = e[i].nxt)
    if (e[i].v != fa)
      dfs(e[i].v, t), lca[++tim][0] = t;
}

void init() {
  for (int i = 2; i <= tim; i <<= 1)
    ++power[i];
  for (int i = 1; i <= tim; ++i)
    power[i] += power[i - 1];
  for (int i = 1; i < 20; ++i)
    for (int j = 1; j <= tim; ++j) {
      ic k = std::min(tim, j + (1 << i - 1));
      lca[j][i] = dep[lca[j][i - 1]] < dep[lca[k][i - 1]] ? lca[j][i - 1]
                                                          : lca[k][i - 1];
    }
}

int get_lca(ic &u, ic &v) {
  ic l = std::min(fi[u], fi[v]), r = std::max(fi[u], fi[v]);
  ic len = power[r - l + 1], k = r - (1 << len) + 1;
  return dep[lca[l][len]] < dep[lca[k][len]] ? lca[l][len] : lca[k][len];
}

int get_dist(ic &u, ic &v) {
  ic lca = get_lca(u, v);
  return dep[u] + dep[v] - 2 * dep[lca];
}

int get_size(ic &t, ic &fa) {
  int ret = 1;
  for (int i = h[t]; i; i = e[i].nxt)
    if (!vis[e[i].v] && e[i].v != fa)
      ret += get_size(e[i].v, t);
  return ret;
}

void get_root(ic &t, ic &fa, ic &tot) {
  size[t] = 1, mx[t] = 0;
  for (int i = h[t]; i; i = e[i].nxt)
    if (!vis[e[i].v] && e[i].v != fa)
      get_root(e[i].v, t, tot), size[t] += size[e[i].v],
          mx[t] = std::max(mx[t], size[e[i].v]);
  (mx[t] = std::max(mx[t], tot - size[t])) < mx[root] && (root = t);
}

void init_heap(ic &t, ic &fa, ic &dep, heap &hp) {
  hp.push(dep);
  for (int i = h[t]; i; i = e[i].nxt)
    if (!vis[e[i].v] && e[i].v != fa)
      init_heap(e[i].v, t, dep + 1, hp);
}

void build(int t) {
  vis[t] = true;
  for (int i = h[t]; i; i = e[i].nxt)
    if (!vis[e[i].v])
      root = 0,
      get_root(e[i].v, 0,
               size[e[i].v] < size[t] ? size[e[i].v] : get_size(e[i].v, t)),
      up[root] = t, init_heap(e[i].v, t, 1, toup[root]),
      me[t].push(toup[root].top()), build(root);
  global.push(me[t].top()), global.push(me[t].top2());
}

void modify(int t) {
  ic p = t;
  if (col[t])
    global.erase(me[t].top());
  else
    global.push(me[t].top());
  for (; up[t]; t = up[t]) {
    if (col[up[t]])
      global.erase(me[up[t]].top());
    global.erase(me[up[t]].top2());
    me[up[t]].erase(toup[t].top());
    if (col[p])
      toup[t].erase(get_dist(p, up[t]));
    else
      toup[t].push(get_dist(p, up[t]));
    me[up[t]].push(toup[t].top());
    if (col[up[t]])
      global.push(me[up[t]].top());
    global.push(me[up[t]].top2());
  }
  col[p] = !col[p];
}
} // namespace tree

int main() {
  read(tree::n), tree::mx[0] = tree::n;
  for (int i = 1, u, v; i < tree::n; ++i)
    read(u), read(v), tree::add_edge(u, v);
  tree::dfs(1, 0), tree::init(), tree::get_root(1, 0, tree::n),
      tree::build(tree::root);
  for (int i = 1; i <= tree::n; ++i)
    tree::col[i] = 1;
  int q;
  for (read(q); q--;) {
    char c;
    scanf(" %c", &c);
    if (c == 'G')
      printf("%d\n", global.top());
    else {
      int p;
      read(p), tree::modify(p);
    }
  }
  return 0;
}

Count on a Tree II

题目描述

You are given a tree with $N$ nodes. The tree nodes are numbered from $1$ to $N$. Each node has an integer weight.
We will ask you to perform the following operation:

  • $u$ $v$: ask for how many different integers that represent the weight of nodes there are on the path from $u$ to $v$.

题意概述

给定一棵$N$个节点的树,每个节点都有权值。有$M$次询问,每次询问给出$u, v$,求从$u$到$v$的路径上有多少种不同的权值。
数据范围:$1 \le N \le 40000, \; 1 \le M \le 10^5$。

算法分析

统计权值种类数,容易想到莫队,但这是在一棵树上,所以需要稍微做些转化。
求出树的括号序(DFS,访问和离开节点时均记录),那么每个询问都可以转化为对括号序上某个区间的询问。但是,如果区间内的某个节点出现了两次,那么这个节点不应该对答案产生贡献。因此,算法执行时可以用两个数组维护,一个表示节点的出现次数,另一个表示权值的出现次数。
具体来讲,令$s_i, e_i$分别表示访问、离开节点$i$的时间。假设$s_u \le s_v$。若$u$是$v$祖先,那么就相当于询问区间$[s_u, s_v]$;否则,相当于询问区间$[e_u, s_v]$,但此时$u, v$的LCA并没有被计算到答案中,因此需要把它加上。

代码

/*
 * Trap full -- please empty.
 */

#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <typename T>
void read(T &n) {
  char c; for (; (c = getchar()) < '0' || c > '9'; ) ;
  for (n = c - '0'; (c = getchar()) >= '0' && c <= '9'; (n *= 10) += c - '0') ;
}

typedef int const ic;
typedef long long ll;

static ic N = 40005;
static ic M = 100005;
static ic K = 300;
std::map <int, int> num;
int nume, h[N], w[N], base[N], seq[N << 1];
int tim, st[N], ed[N], dep[N], up[N][16];
int mans, ml, mr, mvis[N], mrec[N], ans[M];
struct Edge {
  int v, nxt;
} e[N << 1];
struct Query {
  int l, r, lca, id;
  bool operator < (const Query &q) const {
    return l / K == q.l / K ? r < q.r : l / K < q.l / K;
  }
} q[M];

void add_edge(ic &u, ic &v) {
  e[++ nume] = (Edge) { v, h[u] }, h[u] = nume;
  e[++ nume] = (Edge) { u, h[v] }, h[v] = nume;
}

void dfs(ic &t, ic &fa) {
  seq[st[t] = ++ tim] = t, dep[t] = dep[fa] + 1, up[t][0] = fa;
  for (int i = h[t]; i; i = e[i].nxt)
    if (e[i].v != fa) dfs(e[i].v, t);
  seq[ed[t] = ++ tim] = t;
}

int get_lca(int u, int v) {
  if (dep[u] > dep[v]) std::swap(u, v);
  for (int i = 15; ~ i; -- i)
    if (dep[up[v][i]] >= dep[u]) v = up[v][i];
  if (u == v) return u;
  for (int i = 15; ~ i; -- i)
    if (up[u][i] != up[v][i]) u = up[u][i], v = up[v][i];
  return up[u][0];
}

void add(ic &u) {
  if (mvis[u]) {
    -- mrec[w[u]], mvis[u] = 0;
    if (! mrec[w[u]]) -- mans;
  } else {
    if (! mrec[w[u]]) ++ mans;
    ++ mrec[w[u]], mvis[u] = 1;
  }
}

void get(ic &l, ic &r) {
  for (; ml < l;) add(seq[ml ++]);
  for (; ml > l;) add(seq[-- ml]);
  for (; mr < r;) add(seq[++ mr]);
  for (; mr > r;) add(seq[mr --]);
}

int main() {
  int n, m; read(n), read(m);
  for (int i = 1; i <= n; ++ i) {
    read(w[i]);
    if (! num.count(w[i])) num[w[i]] = num.size();
    w[i] = num[w[i]];
  }
  for (int i = 1, u, v; i < n; ++ i) read(u), read(v), add_edge(u, v);
  dfs(1, 0);
  for (int i = 1; i < 16; ++ i)
    for (int j = 1; j <= n; ++ j) up[j][i] = up[up[j][i - 1]][i - 1];
  for (int i = 1, u, v; i <= m; ++ i) {
    read(u), read(v), q[i].id = i;
    if (st[u] > st[v]) std::swap(u, v);
    if (ed[u] > ed[v]) q[i].l = st[u] + 1, q[i].r = st[v], q[i].lca = u;
    else q[i].l = ed[u], q[i].r = st[v], q[i].lca = get_lca(u, v);
  }
  std::sort(q + 1, q + m + 1);
  mans = ml = mr = mvis[1] = mrec[w[1]] = 1;
  for (int i = 1; i <= m; ++ i) get(q[i].l, q[i].r), add(q[i].lca), ans[q[i].id] = mans, add(q[i].lca);
  for (int i = 1; i <= m; ++ i) printf("%d\n", ans[i]);
  return 0;
}

Long Live the Queen

题目描述

The Queen of Byteland is very loved by her people. In order to show her their love, the Bytelanders have decided to conquer a new country which will be named according to the queen’s name. This new country contains $N$ towns. The towns are connected by bidirectional roads and there is exactly ONE path between any two towns, walking on the country’s roads. For each town, the profit it brings to the owner is known. Although the Bytelanders love their queen very much, they don’t want to conquer all the $N$ towns for her. They will be satisfied with a non-empty subset of these towns, with the following $2$ properties: there exists a path from every town in the subset to every other town in the subset walking only through towns in the subset and the profit of the subset is maximum. The profit of a subset of the $N$ towns is equal to the sum of the profits of the towns which belong to the subset. Your task is to find the maximum profit the Bytelanders may get.

题意概述

给定一棵$N$个节点的树,每个节点都有权值。求它连通子图节点权值之和的最大值。
数据范围:$1 \le N \le 16000$。

算法分析

考虑树形DP。假定$1$号点为根节点。令$f_{0, i}$表示$i$的子树中以$i$为根的连通子图节点权值之和的最大值,$f_{1, i}$表示$i$的子树中不以$i$为根的连通子图节点权值之和的最大值。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

namespace std {
  template <typename T> void maxify(T &a, T b) { b > a && (a = b); }
  template <typename T> void minify(T &a, T b) { b < a && (a = b); }
}

struct IOManager {
  template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
  inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
  inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
  template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
  template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
  inline void write(char c) { putchar(c); }
  inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
  template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
  static const int N = 16010;
  int n, nume, h[N], w[N], f[2][N];
  struct Edge {
    int v, nxt;
  } e[N << 1];
  void add_edge(int u, int v) {
    e[++ nume] = (Edge) { v, h[u] }, h[u] = nume;
    e[++ nume] = (Edge) { u, h[v] }, h[v] = nume;
  }
  void input() {
    io > n;
    for (int i = 1; i <= n; ++ i) io > w[i];
    for (int i = 1; i < n; ++ i) {
      int u, v; io > u > v, add_edge(u, v);
    }
  }
  void init() { memset(f, -0x3f, sizeof f); }
  void dfs(int t, int fa) {
    f[0][t] = w[t];
    for (int i = h[t]; i; i = e[i].nxt)
      if (e[i].v != fa) {
        dfs(e[i].v, t);
        maxify(f[1][t], max(f[0][e[i].v], f[1][e[i].v]));
        f[0][t] += max(f[0][e[i].v], 0);
      }
  }
  void process() { dfs(1, 0), io < max(f[0][1], f[1][1]) < '\n'; }

public:
  void solve() { input(), init(), process(); }
} solver;

int main() {
  solver.solve();
  return 0;
}

Petya and Tree

题目描述

One night, having had a hard day at work, Petya saw a nightmare. There was a binary search tree in the dream. But it was not the actual tree that scared Petya. The horrifying thing was that Petya couldn’t search for elements in this tree. Petya tried many times to choose key and look for it in the tree, and each time he arrived at a wrong place. Petya has been racking his brains for long, choosing keys many times, but the result was no better. But the moment before Petya would start to despair, he had an epiphany: every time he was looking for keys, the tree didn’t have the key, and occured exactly one mistake. “That’s not a problem!”, thought Petya. “Why not count the expectation value of an element, which is found when I search for the key”. The moment he was about to do just that, however, Petya suddenly woke up.
Thus, you are given a binary search tree, that is a tree containing some number written in the node. This number is called the node key. The number of children of every node of the tree is equal either to $0$ or to $2$. The nodes that have $0$ children are called leaves and the nodes that have $2$ children, are called inner. An inner node has the left child, that is the child whose key is less than the current node’s key, and the right child, whose key is more than the current node’s key. Also, a key of any node is strictly larger than all the keys of the left subtree of the node and strictly smaller than all the keys of the right subtree of the node.
Also you are given a set of search keys, all of which are distinct and differ from the node keys contained in the tree. For each key from the set its search in the tree is realised. The search is arranged like this: initially we are located in the tree root, if the key of the current node is larger that our search key, then we move to the left child of the node, otherwise we go to the right child of the node and the process is repeated. As it is guaranteed that the search key is not contained in the tree, the search will always finish in some leaf. The key lying in the leaf is declared the search result.
It is known for sure that during the search we make a mistake in comparing exactly once, that is we go the wrong way, but we won’t make any mistakes later. All possible mistakes are equiprobable, that is we should consider all such searches where exactly one mistake occurs. Your task is to find the expectation (the average value) of the search result for every search key, considering that exactly one mistake occurs in the search. That is, for a set of paths containing exactly one mistake in the given key search, you should count the average value of keys containing in the leaves of those paths.

题意概述

给定一棵包含$n$个节点的二叉搜索树,每个节点都有$0$个或$2$个儿子。如果一个节点有儿子,那么它左子树中的所有节点的值都严格小于这个节点,它右子树中的所有节点的值都严格大于这个节点。由于一些差错,这棵搜索树在查找一个值时总是会犯恰好一次错误——应该往左查找时却往右查找,应该往右查找时却往左查找。现有$k$个树中不存在的值待查找,求每一次查找得到的数的期望。
数据范围:$3 \le n \lt 10^5, \; 1 \le k \le 10^5$。

算法分析

很容易想到暴力的方法:先DFS预处理出每棵子树中的最大值和最小值,接着对于每一个待查找的值,直接在树中查找;若应该往左子树走,则将答案加上右子树中的最小值,否则加上左子树中的最大值,然后往正确的方向走。由于这并不是一棵平衡树,因此最坏情况的时间复杂度为$O(n^2)$。
搜索树中的数将数字划分成了$(n+1)$个区间。对于每一个区间而言,其答案都是一样的。因此,我们可以再进行一次DFS,处理出每个区间的答案。处理方法类似于暴力,但是搜索完一棵子树后需要回溯。最后查找$k$个数时,只需对每个数二分查找属于哪个区间,并输出那个区间的答案。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
struct node_type {
  long long val, min, max, child[2];
} node[100001];
long long n, k, cnt, times, root, top, id[100001];
double ans[100001];
void dfs(long long t) {
  if (!node[t].child[0]) {
    node[t].min = node[t].max = node[t].val; return;
  }
  dfs(node[t].child[0]), dfs(node[t].child[1]);
  node[t].min = node[node[t].child[0]].min, node[t].max = node[node[t].child[1]].max;
}
void find(long long t) {
  if (!node[t].child[0]) {
    id[top] = node[t].val, ans[top++] = 1.0 * cnt / times; return;
  }
  cnt += node[node[t].child[1]].min, ++times, find(node[t].child[0]), id[top++] = node[t].val;
  cnt += node[node[t].child[0]].max - node[node[t].child[1]].min, find(node[t].child[1]);
  cnt -= node[node[t].child[0]].max, --times;
}
int main()
{
  scanf("%lld", &n);
  for (int i = 1; i <= n; ++i) {
    long long a; scanf("%lld%lld", &a, &node[i].val);
    if (a == -1) root = i;
    else if (!node[a].child[0]) node[a].child[0] = i;
      else {
        node[a].child[1] = i;
        if (node[node[a].child[0]].val > node[node[a].child[1]].val)
          node[a].child[0] ^= node[a].child[1] ^= node[a].child[0] ^= node[a].child[1];
      }
  }
  dfs(root), find(root), scanf("%lld", &k);
  for (int i = top - 2; i >= 0; --i) if (!ans[i]) ans[i] = ans[i + 1];
  while (k--) {
    long long a, l = 0, r = top; scanf("%lld", &a);
    while (l + 1 < r) {
      long long mid = l + r >> 1; if (id[mid] < a) l = mid; else r = mid;
    }
    printf("%.10lf\n", ans[l]);
  }
  return 0;
}

High Load

题目描述

Arkady needs your help again! This time he decided to build his own high-speed Internet exchange point. It should consist of $n$ nodes connected with minimum possible number of wires into one network (a wire directly connects two nodes). Exactly $k$ of the nodes should be exit-nodes, that means that each of them should be connected to exactly one other node of the network, while all other nodes should be connected to at least two nodes in order to increase the system stability.
Arkady wants to make the system as fast as possible, so he wants to minimize the maximum distance between two exit-nodes. The distance between two nodes is the number of wires a package needs to go through between those two nodes.
Help Arkady to find such a way to build the network that the distance between the two most distant exit-nodes is as small as possible.

题意概述

构造一棵有$n$个节点的树,使得这棵树恰有$k$个叶子节点,且直径最小。
数据范围:$3 \le n \le 2 \times 10^5, \; 2 \le k \le n-1$。

算法分析

首先确定一个根节点,从它引出$k$个叶子节点。接着从这$k$个叶子节点一层一层往外扩展,每次扩展一个节点,直到树中的节点数为$n$。此时树的直径就是深度最大的两个节点的深度和。证明如下:

假设根节点连出的某棵子树中有两个以上的叶子节点,我们可以找出它们的LCA,并将LCA和它到根节点路径上的所有点“分裂”成两个节点。由于这个操作使得树中的节点数增加,因此需要删去一些叶子节点。这样并不会使树的直径增加。

由此得证。

代码

#include <cstdio>
#include <queue>
using namespace std;
struct edge {
  int v, nxt;
} e[400001];
int n, m, nume, h[200001], depth[200001];
queue<int> que;
void add_edge(int u, int v) {
  e[++nume].v = v, e[nume].nxt = h[u], h[u] = nume;
}
int main()
{
  scanf("%d%d", &n, &m);;
  for (int i = 1; i <= m; ++i) {
    add_edge(1, i + 1), depth[i + 1] = 1;
    que.push(i + 1);
  }
  for (int i = m + 2; i <= n; ++i) {
    int u = que.front(); que.pop();
    add_edge(u, i), depth[i] = depth[u] + 1;
    que.push(i);
  }
  printf("%d\n", depth[n] + depth[n - 1]);
  for (int i = 1; i <= n; ++i) {
    for (int j = h[i]; j; j = e[j].nxt) {
      printf("%d %d\n", i, e[j].v);
    }
  }
  return 0;
}

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;
}

Query on the Subtree

题目描述

Bobo has a tree, whose vertices are conveniently labeled by $1, 2, \ldots, n$. At the very begining, the $i$-th vertex is assigned with weight $w_i$.
There are $q$ operations. Each operations are of the following $2$ types:

  • change the weight of vertex $v$ into $x$ (denoted as “! $v$ $x$”),
  • ask the total weight of vertices whose distance are no more than $d$ away from vertex $v$ (denoted as “? $v$ $d$”).

Note that the distance between vertex $u$ and $v$ is the number of edges on the shortest path between them.

题意概述

给定一棵有$n$个节点的树,第$i$个节点的权值为$w_i$。有两种操作:①将节点$v$的权值变成$x$;②询问与节点$v$的距离不超过$d$的所有节点的权值和。共有$q$次操作。
数据范围:$1 \le n, q \le 10^5, \; 0 \le w_i \le 10^4, \; 0 \le x \le 10^4, \; 0 \le d \le n$。

算法分析

对于我们枚举的某一个重心$x$,从它子树的重心向它连一条“虚”边,这样就形成了一棵由重心相连构成的“重心树”。由重心的性质可得,这棵树最多只有$O(\log n)$层。
A Weight Tree
如图,黑色表示原树上的边,红色表示重心树上的“虚”边。
对于每个节点,我们用树状数组存下它在“重心树”上的子树节点到它的距离为$p$(在原树上的距离)的权值和。当我们询问到节点$v$的距离不超过$d$的节点的权值和时,答案就等于$v$的树状数组中$d$的前缀和,再加上“重心树”上$v$的祖先节点$u$的树状数组中$d-dist_{u, v}$的前缀和。可以发现,$u$在“重心树”上包含$v$的子树中的节点被重复计算了。
如图,在计算到节点$3$的距离不超过$3$的节点的权值和时,计算了节点$3$子树中的节点$1, 3, 6, 8$;在计算到节点$3$的祖先节点$2$的距离不超过$3-2=1$的节点的权值和时,节点$1$又被计算了一次。
根据容斥原理,只需对每个节点再用一个树状数组记录下它在“重心树”上的子树节点到它在“重心树”上的父节点的距离为$p$(在原树上的距离)的权值和,每次计算时减去这个树状数组中$d-dist_{u, v}$的前缀和,就得到了正确答案。
修改节点$v$的权值时,只需更新“重心树”上$v$所有祖先节点的树状数组即可。
树上两点间的距离可以通过倍增求LCA得到,不过有更简便的方法。由于每个节点只会被$O(\log n)$个重心搜到,因此可以存下每个节点到其所有祖先重心节点的距离。
在“重心树”上操作的时间复杂度为$O(\log n)$,树状数组的时间复杂度为$O(\log n)$,总时间复杂度为$O(q\log^2n)$。
“重心树”上每一层节点的树状数组空间复杂度为$O(n)$,有$O(\log n)$层,每个节点上要存$O(\log n)$个距离,总空间复杂度为$O(n\log n)$。

代码

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
struct edge {
    int v, nxt;
} e[200001];
struct binary_indexed_tree {
    int n;
    vector<int> a;
    void init(int size) { n = size + 10, a.clear(), a.resize(n); }
    void add(int p, int t) {
        if (p) for (int i = p; i < n; i += i & -i) a[i] += t;
    }
    int sum(int p) {
        if (p <= 0) return 0;
        int ret = 0;
        for (int i = min(p, n - 1); i; i -= i & -i) ret += a[i];
        return ret;
    }
} tree[200001];
int n, q, nume, tot, top, root, h[100001], w[100001];
int size[100001], f[100001], up[100001], id[100001][2];
bool vis[100001];
vector<int> dist[100001];
void add_edge(int u, int v) {
    e[++nume].v = v, e[nume].nxt = h[u], h[u] = nume;
    e[++nume].v = u, e[nume].nxt = h[v], h[v] = nume;
}
void get_root(int t, int fa) {
    size[t] = 1, f[t] = 0;
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v] && e[i].v != fa) {
            get_root(e[i].v, t);
            size[t] += size[e[i].v], f[t] = max(f[t], size[e[i].v]);
        }
    }
    f[t] = max(f[t], tot - size[t]);
    if (f[t] < f[root]) root = t;
}
void get_dist(int t, int fa, int depth, int flag) {
    if (flag) dist[t].push_back(depth);
    else {
        tree[id[root][0]].add(depth, w[t]);
        if (dist[t].size() > 1) tree[id[root][1]].add(dist[t][dist[t].size() - 2], w[t]);
    }
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v] && e[i].v != fa) get_dist(e[i].v, t, depth + 1, flag);
    }
}
void solve(int t) {
    vis[t] = true;
    for (int i = h[t]; i; i = e[i].nxt) if (!vis[e[i].v]) get_dist(e[i].v, t, 1, 0);
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v]) {
            root = 0, tot = size[e[i].v], get_root(e[i].v, t), up[root] = t;
            tree[id[root][0] = ++top].init(size[e[i].v]);
            tree[id[root][1] = ++top].init(size[e[i].v]);
            tree[id[root][1]].add(dist[root][dist[root].size() - 1], w[root]);
            get_dist(root, 0, 0, 1);
            solve(root);
        }
    }
}
void modify(int t, int d) {
    int p = t, top = dist[t].size() - 1;
    while (p) {
        if (top >= 0) tree[id[p][0]].add(dist[t][top], d);
        if (top > 0) tree[id[p][1]].add(dist[t][top - 1], d);
        p = up[p], --top;
    }
}
int ask(int t, int d) {
    int p = t, ret = 0, top = dist[t].size() - 1;
    while (p) {
        int len;
        if (top >= 0) len = d - dist[t][top];
        if (top >= 0 && len >= 0) ret += tree[id[p][0]].sum(len) + w[p];
        if (top > 0) len = d - dist[t][top - 1];
        if (top > 0 && len >= 0 && up[p]) ret -= tree[id[p][1]].sum(len);
        p = up[p], --top;
    }
    return ret;
}
int main()
{
    while (scanf("%d%d", &n, &q) != EOF) {
        nume = top = 0;
        memset(up, 0, sizeof(up));
        memset(h, 0, sizeof(h));
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &w[i]);
            dist[i].clear();
        }
        for (int i = 1; i < n; ++i) {
            int u, v;
            scanf("%d%d", &u, &v), add_edge(u, v);
        }
        root = 0, tot = f[0] = n, get_root(1, 0);
        tree[id[root][0] = ++top].init(size[1]);
        tree[id[root][1] = ++top].init(size[1]);
        get_dist(root, 0, 0, 1);
        solve(root);
        while (q--) {
            char oper = ' ';
            while (oper != '!' && oper != '?') scanf("%c", &oper);
            int v, d;
            scanf("%d%d", &v, &d);
            if (oper == '!') modify(v, d - w[v]), w[v] = d;
            else printf("%d\n", ask(v, d));
        }
    }
    return 0;
}

Digit Tree

题目描述

ZS the Coder has a large tree. It can be represented as an undirected connected graph of $n$ vertices numbered from $0$ to $n-1$ and $n-1$ edges between them. There is a single nonzero digit written on each edge.
One day, ZS the Coder was bored and decided to investigate some properties of the tree. He chose a positive integer $M$, which is coprime to $10$, i.e. $(M, 10)=1$.
ZS consider an ordered pair of distinct vertices $(u, v)$ interesting when if he would follow the shortest path from vertex $u$ to vertex $v$ and write down all the digits he encounters on his path in the same order, he will get a decimal representaion of an integer divisible by $M$.
Formally, ZS consider an ordered pair of distinct vertices $(u, v)$ interesting if the following states true:

  • let $a_1=u, a_2, \ldots, a_k=v$ be the sequence of vertices on the shortest path from $u$ to $v$ in the order of encountering them;
  • let $d_i (1 \le i \lt k)$ be the digit written on the edge between vertices $a_i$ and $a_i+1$;
  • the integer $\overline{d_1d_2 \ldots d_{k-1}}=\sum_{i=1}^{k-1} 10^{k-1-i}d_i$ is divisible by $M$.

Help ZS the Coder find the number of interesting pairs!

题意概述

给定一棵有$n$个节点的树和一个与$10$互质的数$M$,树上每条边的权值都是小于$10$的正整数。定义$dist_{u, v}$为依次写下从$u$到$v$路径上每条边的权值所得到的数字。求满足$M \mid dist_{u, v}$的点对个数。
数据范围:$2 \le n \le 10^5, \; 1 \le M \le 10^9$。

算法分析

设当前枚举到的节点为$x$。令$depth_u$表示$u$在$x$及它子树中的深度。对于在$x$第$(i+1)$棵子树中的节点$u$和在前$i$棵子树中的节点$v$,有:
$$
\begin{align}
M \mid dist_{u, v} \Leftrightarrow 10^{depth_v}dist_{u, x}+dist_{x, v} \equiv 0 \pmod M \tag{1} \\
M \mid dist_{v, u} \Leftrightarrow 10^{depth_u}dist_{v, x}+dist_{x, u} \equiv 0 \pmod M \tag{2}
\end{align}
$$
对于$(1)$式,化简得$dist_{u, x} \equiv -10^{-depth_v}dist_{x, v} \pmod M$;对于$(2)$式,化简得$10^{-depth_u}dist_{x, u} \equiv -dist_{v, x} \pmod M$。用两个map分别存下前$i$棵子树中$10^{-depth_v}dist_{x, v}$和$dist_{v, x}$的值,在处理第$(i+1)$棵子树时直接加上可行的方案数。

代码

#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
struct edge {
    int v, w, nxt;
} e[200001];
long long n, m, ans, nume, tot, root, h[100001], size[100001], f[100001];
long long val1[100001], val2[100001], power[100001], inv[100001];
bool vis[100001];
map<long long, int> id1, id2;
void extend_gcd(int a, int b, int &x, int &y) {
    if (!b) { x = 1, y = 0; return; }
    extend_gcd(b, a % b, y, x);
    y -= a / b * x;
}
void add_edge(int u, int v, int w) {
    e[++nume].v = v, e[nume].w = w, e[nume].nxt = h[u], h[u] = nume;
    e[++nume].v = u, e[nume].w = w, e[nume].nxt = h[v], h[v] = nume;
}
void get_root(int t, int fa) {
    size[t] = 1, f[t] = 0;
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v] && e[i].v != fa) {
            get_root(e[i].v, t);
            size[t] += size[e[i].v];
            f[t] = max(f[t], size[e[i].v]);
        }
    }
    f[t] = max(f[t], tot - size[t]);
    if (f[t] < f[root]) root = t;
}
void get_dist(int t, int fa, int flag, int depth) {
    if (!flag) ++id1[val1[t]], ++id2[val2[t] * inv[depth] % m];
    else {
        ans += !val1[t] + !val2[t];
        ans += id1[(val2[t] ? m - val2[t] : 0) * inv[depth] % m];
        ans += id2[val1[t] ? m - val1[t] : 0];
    }
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v] && e[i].v != fa) {
            if (flag) {
                val1[e[i].v] = (val1[t] + e[i].w * power[depth]) % m;
                val2[e[i].v] = (val2[t] * 10 + e[i].w) % m;
            }
            get_dist(e[i].v, t, flag, depth + 1);
        }
    }
}
void solve(int t) {
    vis[t] = true, id1.clear(), id2.clear();
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v]) {
            val1[e[i].v] = val2[e[i].v] = e[i].w % m;
            get_dist(e[i].v, t, 1, 1);
            get_dist(e[i].v, t, 0, 1);
        }
    }
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v]) {
            root = n, tot = size[e[i].v];
            get_root(e[i].v, t);
            solve(root);
        }
    }
}
int main()
{
    scanf("%lld%lld", &n, &m);
    power[0] = 1;
    for (int i = 1; i <= n; ++i) power[i] = power[i - 1] * 10 % m;
    for (int i = 0; i <= n; ++i) {
        int x, y;
        extend_gcd(power[i], m, x, y);
        inv[i] = (x % m + m) % m;
    }
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w);
    }
    tot = f[n] = n, root = n;
    get_root(0, n);
    solve(root);
    printf("%lld\n", ans);
    return 0;
}

D Tree

题目描述

There is a skyscraping tree standing on the playground of Nanjing University of Science and Technology. On each branch of the tree is an integer (The tree can be treated as a connected graph with $N$ vertices, while each branch can be treated as a vertex). Today the students under the tree are considering a problem: Can we find such a chain on the tree so that the multiplication of all integers on the chain (mod $10^6 + 3$) equals to $K$?
Can you help them in solving this problem?

题意概述

给定一棵有$N$个节点的树,其中第$i$个节点的权值为$v_i$。求一个字典序最小的点对使得这两点之间路径上的点权之积模$10^6+3$等于$K$。
数据范围:$1 \le N \le 10^5, \; 0 \le K \lt 10^6+3, \; 1 \le v_i \lt 10^6+3$。

算法分析

点分治。设当前枚举到的节点为$x$,其第$i$棵子树的根节点为$x_i$。用map储存下$x$前$i$棵子树中的节点到$x$儿子的可能的乘积。在计算第$(i+1)$棵子树时,设当前计算的节点到$x_{i+1}$的乘积为$p$,若map中存在$q$满足$p \times q \times x \equiv K \pmod {10^6+3}$,即$q \equiv K \times p^{-1} \times x^{-1} \pmod {10^6+3}$,则将这两个节点与当前答案比较,取较优解。

代码

#include <cstdio>
#include <map>
#include <algorithm>
#include <cstring>
#define MOD 1000003
using namespace std;
struct edge {
    int v, nxt;
} e[200001];
long long n, k, x, y, root, nume, tot, inv[MOD], h[100001], v[100001], size[100001], f[100001], val[100001];
bool vis[100001];
map<long long, int> id;
void add_edge(int u, int v) {
    e[++nume].v = v, e[nume].nxt = h[u], h[u] = nume;
    e[++nume].v = u, e[nume].nxt = h[v], h[v] = nume;
}
void get_root(int t, int fa) {
    size[t] = 1, f[t] = 0;
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v] && e[i].v != fa) {
            get_root(e[i].v, t);
            size[t] += size[e[i].v];
            f[t] = max(f[t], size[e[i].v]);
        }
    }
    f[t] = max(f[t], tot - size[t]);
    if (f[t] < f[root]) root = t;
}
void update(int a, int b) {
    if (a > b) swap(a, b);
    if (a < x) x = a, y = b;
    else if (a == x && b < y) y = b;
}
void get_dist(int t, int fa, int flag) {
    if (!flag) {
        if (!id.count(val[t])) id[val[t]] = t;
        else id[val[t]] = min(id[val[t]], t);
    } else {
        if (val[t] * val[root] % MOD == k) {
            if (t <= x || root <= x) update(t, root);
        }
        long long inverse = k * inv[val[t]] % MOD * inv[val[root]] % MOD;
        if (id.count(inverse)) {
            if (id[inverse] <= x || t <= x) update(id[inverse], t);
        }
    }
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v] && e[i].v != fa) {
            if (flag) val[e[i].v] = val[t] * v[e[i].v] % MOD;
            get_dist(e[i].v, t, flag);
        }
    }
}
void solve(int t) {
    vis[t] = true, val[t] = v[t], id.clear();
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v]) {
            val[e[i].v] = v[e[i].v];
            get_dist(e[i].v, t, 1);
            get_dist(e[i].v, t, 0);
        }
    }
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v]) {
            root = 0, tot = size[e[i].v];
            get_root(e[i].v, t);
            solve(root);
        }
    }
}
int main()
{
    inv[1] = 1;
    for (int i = 2; i < MOD; ++i) {
        inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
    }
    while (scanf("%lld%lld", &n, &k) != -1) {
        x = y = 1e9, nume = 0;
        memset(vis, 0, sizeof(vis));
        memset(h, 0, sizeof(h));
        for (int i = 1; i <= n; ++i) scanf("%lld", &v[i]);
        for (int i = 1; i < n; ++i) {
            int u, v;
            scanf("%d%d", &u, &v);
            add_edge(u, v);
        }
        tot = f[0] = n, root = 0;
        get_root(1, 0);
        solve(root);
        if (y <= n) printf("%lld %lld\n", x, y);
        else printf("No solution\n");
    }
    return 0;
}

Tree

题目描述

Give a tree with $n$ vertices, each edge has a length (positive integer less than $1001$).
Define $dist(u, v)= \text{The min distance between node} \; u \; \text{and} \; v$.
Give an integer $k$, for every pair $(u, v)$ of vertices is called valid if and only if $dist(u, v)$ not exceed $k$.
Write a program that will count how many pairs which are valid for a given tree.

题意概述

给定一棵有$n$个节点的树以及每条边的权值,问有多少个点对之间的距离不大于$k$。
数据范围:$2 \le n \le 10000$。

算法分析

考虑对于一个节点$x$以及它的子树,其中距离不大于$k$的点对要么在$x$的同一棵子树中,要么在$x$的不同子树中。后者可以递归解决,下面来解决前者。
可以统计出子树中每个节点到$x$的距离$dist_{u, x}$。显然有
$$dist_{u, v} \le k \text{且路径经过} x \Leftrightarrow dist_{u, x} + dist_{x, v} \le k \text{且} u \text{和} v \text{在不同子树中}$$
枚举$x$的子树,将前$i$棵子树中所有节点到$x$的距离用Treap维护,在处理第$(i+1)$棵子树的节点$t$时把答案加上Treap中小于等于$k-dist_{t, x}$的数的个数,即可得到答案。

代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct edge {
    int v, w, nxt;
} e[20001];
struct treap {
    int tot, root;
    struct node_type {
        int val, cnt, size, rank, child[2];
    } a[10001];
    void init() { tot = root = 0; }
    void update(int t) { a[t].size = a[a[t].child[0]].size + a[a[t].child[1]].size + a[t].cnt; }
    void turn(int &t, int dire) {
        int p = a[t].child[!dire];
        a[t].child[!dire] = a[p].child[dire], a[p].child[dire] = t;
        update(t), update(p), t = p;
    }
    void insert(int &t, int val) {
        if (!t) {
            t = ++tot, a[t].rank = rand(), a[t].cnt = a[t].size = 1, a[t].val = val;
            a[t].child[0] = a[t].child[1] = 0;
            return;
        }
        ++a[t].size;
        if (val == a[t].val) ++a[t].cnt;
        else if (val < a[t].val) {
            insert(a[t].child[0], val);
            if (a[a[t].child[0]].rank < a[t].rank) turn(t, 1);
        } else {
            insert(a[t].child[1], val);
            if (a[a[t].child[1]].rank < a[t].rank) turn(t, 0);
        }
    }
    int query(int t, int val) {
        if (!t) return 0;
        if (val == a[t].val) return a[a[t].child[0]].size;
        else if (val < a[t].val) return query(a[t].child[0], val);
        else return a[a[t].child[0]].size + a[t].cnt + query(a[t].child[1], val);
    }
} tree;
long long n, k, nume, root, tot, ans, h[10001], size[10001], f[10001], val[10001];
bool vis[10001];
void add_edge(int u, int v, int w) {
    e[++nume].v = v, e[nume].w = w, e[nume].nxt = h[u], h[u] = nume;
    e[++nume].v = u, e[nume].w = w, e[nume].nxt = h[v], h[v] = nume;
}
void get_root(int t, int fa) {
    size[t] = 1, f[t] = 0;
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v] && e[i].v != fa) {
            get_root(e[i].v, t);
            size[t] += size[e[i].v];
            f[t] = max(f[t], size[e[i].v]);
        }
    }
    f[t] = max(f[t], tot - size[t]);
    if (f[t] < f[root]) root = t;
}
void get_dist(int t, int fa, int flag) {
    if (!flag) tree.insert(tree.root, val[t]);
    else ans += tree.query(tree.root, k - val[t] + 1);
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v] && e[i].v != fa) {
            val[e[i].v] = val[t] + e[i].w;
            get_dist(e[i].v, t, flag);
        }
    }
}
void solve(int t) {
    vis[t] = true;
    tree.init(), tree.insert(tree.root, 0);
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v]) {
            val[e[i].v] = e[i].w;
            get_dist(e[i].v, t, 1);
            get_dist(e[i].v, t, 0);
        }
    }
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v]) {
            root = 0, tot = size[e[i].v];
            get_root(e[i].v, t);
            solve(root);
        }
    }
}
int main()
{
    while (scanf("%lld%lld", &n, &k)) {
        if (!n) break;
        memset(vis, 0, sizeof(vis));
        memset(h, 0, sizeof(h));
        ans = nume = 0;
        for (int i = 1; i < n; ++i) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            add_edge(u ,v, w);
        }
        tot = f[0] = n, root = 0;
        get_root(1, 0);
        solve(root);
        printf("%lld\n", ans);
    }
    return 0;
}