# [POJ 1741] Tree 点分治

## 题意

给定 n 个节点的树.

求有多少对节点 (u, v) , 满足 dist(u, v) <= K .

n <= 10000.

## 实现

```#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
#define F(i, a, b) for (register int i = (a); i <= (b); i++)
inline int rd(void) {
int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == ‘-‘) f = -1;
int x = 0; for (; isdigit(c); c = getchar()) x = x*10+c-‘0‘; return x*f;
}

const int N = 10005;

#define fore(it, x) for (register vector<E>::iterator it = g[x].begin(); it != g[x].end(); it++)
int n, K;
struct E { int v, d; inline E(int _v = 0, int _d = 0): v(_v), d(_d) {} }; vector<E> g[N];
inline void Init(int u, int v, int d) { g[u].push_back(E(v, d)), g[v].push_back(E(u, d)); }

int siz[N], num; bool vis[N];
int s[N], top;
int res;

inline int Siz(int x, int par) {
siz[x] = 1;
fore(it, x) if (!vis[it->v] && it->v != par)
siz[x] += Siz(it->v, x);
return siz[x];
}
inline int Root(int x, int par) {
fore(it, x) if (!vis[it->v] && it->v != par) {
if (siz[it->v] > (num >> 1)) return Root(it->v, x);
}
return x;
}

inline void List(int x, int par, int Dist) {
s[++top] = Dist;
fore(it, x) if (!vis[it->v] && it->v != par)
List(it->v, x, Dist + it->d);
}
inline int Calc(int x, int par, int Dist, int sign) {
top = 0, List(x, par, Dist);
sort(s+1, s+top+1);
int sum = 0;
for (int i = top, j = 0; i >= 1; i--) {
while (j < i && s[i]+s[j+1] <= K) j++;
if (i == j) j--;
sum += j;
}
return sum * sign;
}

void Solve(int f) {
num = Siz(f, -1);
int x = Root(f, -1);

res += Calc(x, -1, 0, +1);
fore(it, x) if (!vis[it->v])
res += Calc(it->v, x, it->d, -1);

vis[x] = true;
fore(it, x) if (!vis[it->v])
Solve(it->v);
}

int main(void) {
for (n = rd(), K = rd(); n > 0 || K > 0; n = rd(), K = rd()) {
F(i, 1, n-1) {
int u = rd(), v = rd(), d = rd();
Init(u, v, d);
}

memset(vis, 0, sizeof vis), res = 0;
Solve(1);
printf("%d\n", res);

F(i, 1, n) g[i].clear();
}
return 0;
}```

## POJ 1741 Tree ——点分治

[题目分析] 这貌似是做过第三道以Tree命名的题目了. 听说树分治的代码都很长,一直吓得不敢写,有生之年终于切掉这题. 点分治模板题目.自己YY了好久才写出来. 然后1A了,开心o(*￣▽￣*)ブ [代码] #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define maxn 20005 #define inf 0x3f3f3f3f using

## POJ 1741 Tree(树的点分治，入门题)

Tree Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 21357   Accepted: 7006 Description Give a tree with n vertices,each edge has a length(positive integer less than 1001).Define dist(u,v)=The min distance between node u and v.Give an in

## 数据结构（树，点分治）：POJ 1741 Tree

Description Give a tree with n vertices,each edge has a length(positive integer less than 1001). Define dist(u,v)=The min distance between node u and v. Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not e