題目連結：
Tree
題意：
給定一棵樹，每條邊有一個權值，求樹上長度 <=k 的路徑條數。
思路：
樹的點分治例題。
參考部落格：【算法學習】點分治
計算一棵以 A 為根的樹上長度 <=k 的路徑條數可分為 2 個部分：
1. 路徑經過 A 點。
2. 路徑不經過 A 點。
可以看出第 2 種情況是以A的子樹中的點為根節點時的情況 1 。是以每次計算以一個點為根時的第一種情況，dfs遞歸計算即可。
考慮經過 A 的邊：A，A->B，A->B->D，A->B->E，A->C，A->C->F 。
上述 2 條邊可以合成 1 條路徑（因為有A這條相當于不存在的邊，是以2條邊合成的邊中也包括了從A開始的鍊）。
把這些權值都存下來，排序，周遊這些權值（設目前為 i ），每次二分找到第一個與第 i 個相加大于 k 的位置 pos ，則有pos-i-1種情況滿足和<=k。複雜度O(nlogn) 。
當然，上述計算的結果中包含非法情況，如 A->B 不能與 A->B->D 合成一條路徑。這種情況都出現在 A 的一棵子樹中兩條邊進行了組合。考慮去除非法的路徑，對于根節點的每個子節點代表的子樹，按照同樣方式統計答案，并把得出的結果從原來的答案中減去即可。其中還要考慮子樹的路徑長度，剛才對根的計算時，子樹的所有路徑長都加上了根到子樹的邊的權值。那麼在對這棵子樹計算時，注意子樹的路徑也都要加上這條邊的權值，這樣正好和原來的路徑長度吻合。設每棵子樹大小為siz[i]，複雜度<= O(siz[1]*logn+siz[2]*logn+...+siz[t]*logn) <= O((siz[1]+siz[2]+...+siz[t])*logn) <= O(nlogn)
是以，這樣對于以一個點為根節點的情況就可以在O(nlogn)的情況下求得了。
接下來求其所有子節點為根節點的情況。且其子節點求解時與該點無關。
但這樣看來要求 n 個點，複雜度爆炸。點分治的關鍵來了，每次選的點為樹的重心。
樹的重心介紹見：樹的重心
其滿足一個性質：以樹的重心為根的有根樹，最大子樹大小不超過
。
是以，我們每次找到樹的重心作為根節點，計算答案。再把其所有子樹按這種方法求解（因為其子節點求解時與該點無關）。
對于一個點所有子樹（即樹的一層）計算完的複雜度為O(nlogn)（證明方法同去除非法情況時的複雜度計算）
因為每次找的都是重心，是以最多計算 logn 層，是以總複雜度為 O(n*logn*logn) 。
總結：點分治，顧名思義就是每個點分别計算，但通過每次選取子樹重心為新根來減小樹的高度，進而來降低複雜度。是一種巧妙的暴力。
坑點再代碼注釋中給出。
Code：
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX = 10000 + 10;
const ll mod = 1e9 + 7;
typedef struct {
int to, val;
}Point;
int n, k;
vector<Point>mp[MAX];
vector<int>num;
int siz[MAX], dis[MAX], vis[MAX];
int rt, minsubtree, nodenum;
int ans;
//求樹的重心
void find_root(int root, int fa)
{
siz[root] = 1;
int maxsubtree = 0;
for (int i = 0; i < mp[root].size(); i++) {
int v = mp[root][i].to;
if (v == fa) continue;
if (vis[v]) continue;
find_root(v, root);
siz[root] += siz[v];
maxsubtree = max(maxsubtree, siz[v]);
}
//注意總節點個數不是一直為n
maxsubtree = max(maxsubtree, nodenum - siz[root]);
if (maxsubtree < minsubtree) {
rt = root;
minsubtree = maxsubtree;
}
}
//求以一個點為根節點時經過它的所有邊
void dfs(int root, int fa)
{
for (int i = 0; i < mp[root].size(); i++) {
int v = mp[root][i].to;
if (v == fa) continue;
if (vis[v]) continue;
dis[v] = dis[root] + mp[root][i].val;
num.push_back(dis[v]);
dfs(v, root);
}
}
//計算以一個點為根節點時的答案（總：含非法情況）
int f()
{
sort(num.begin(), num.end());
ll sum = 0;
int tot = num.size();
for (int i = 0; i < tot - 1; i++) {
if (num[i] >= k) {
continue;
}
int pos = upper_bound(num.begin() + i + 1, num.end(), k - num[i]) - num.begin();
sum += (pos - 1 - (i + 1) + 1);
}
return sum;
}
//計算以一個點為根節點時的答案（去除非法情況）
void cul(int root, int fa)
{
num.clear();
dis[root] = 0;
num.push_back(0);
dfs(root, fa);
if (num.size() == 1)
return;
ans += f();
for (int i = 0; i < mp[root].size(); i++) {
int v = mp[root][i].to;
if (v == fa) continue;
if (vis[v]) continue;
num.clear();
dis[v] = mp[root][i].val;
num.push_back(dis[v]);
dfs(v, root);
ans -= f();
}
}
//以每個點為根節點進行計算
void solve(int root, int fa)
{
vis[root] = 1;
cul(root, fa);
for (int i = 0; i < mp[root].size(); i++) {
int v = mp[root][i].to;
if (v == fa) continue;
if (vis[v]) continue;
minsubtree = 1e9 + 7;
nodenum = siz[v];
//每次取其子樹的重心為根
find_root(v, root);
solve(rt, -1);
}
}
int main()
{
while (scanf("%d%d", &n, &k), n || k)
{
memset(vis, 0, sizeof(vis));
//注意vector的初始化，RE就是忘了這個
for (int i = 1; i <= n; i++) {
mp[i].clear();
}
for (int i = 1; i < n; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
Point tmp;
tmp.to = v;
tmp.val = w;
mp[u].push_back(tmp);
tmp.to = u;
mp[v].push_back(tmp);
}
rt = 1;
minsubtree = 1e9 + 7;
ans = 0;
nodenum = n;
find_root(1, -1);
solve(rt, -1);
printf("%d\n", ans);
}
return 0;
}