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

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