poj2106，POJ1741 Tree（點分治）

嘟嘟嘟

沒錯，這一道最經典的點分治模板題。
題意：求樹上兩點間距離\(\leqslant k\)的點對個數。

點分治這東西我好早就聽說了，然后一兩個月前也學了一下，不過只是刷了個模板，沒往深處學。
對于這道題，就說說大概的步驟吧。
1.找重心：一遍\(dfs\)即可。
2.求出每一個子樹中的點到重心的距離。并且記錄這個點屬于哪一棵子樹。
3.把上述的點存下來，按距離從小到大排序。
4.統計答案。采用雙指針，\(i\)從頭開始，\(j\)從尾開始。這樣每一個\(i\)對答案的貢獻是\(j - i - num[point_i]\)，\(num[point_i]\)表示的是\(i\)所在的子樹有多少個。（為了減去屬于相同子樹的貢獻）
5.遞歸到每一個子樹中統計答案。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("") 
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 4e4 + 5;
inline ll read()
{ll ans = 0;char ch = getchar(), last = ' ';while(!isdigit(ch)) last = ch, ch = getchar();while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();if(last == '-') ans = -ans;return ans;
}
inline void write(ll x)
{if(x < 0) x = -x, putchar('-');if(x >= 10) write(x / 10);putchar(x % 10 + '0');
}int n, k;
struct Edge
{int nxt, to, w;
}e[maxn << 1];
int head[maxn], ecnt = -1;
void addEdge(int x, int y, int w)
{e[++ecnt] = (Edge){head[x], y, w};head[x] = ecnt;
}bool out[maxn];
int Siz, siz[maxn], Max[maxn];
void dfs1(int now, int _f, int &cg)
{siz[now] = 1; Max[now] = -1;for(int i = head[now], v; i != -1; i = e[i].nxt){if(!out[v = e[i].to] && v != _f){dfs1(v, now, cg);siz[now] += siz[v];Max[now] = max(Max[now], siz[v]);}}Max[now] = max(Max[now], Siz - siz[now]);if(!cg || Max[now] < Max[cg]) cg = now;
}struct Node
{int dis, bel;bool operator < (const Node& oth)const{return dis < oth.dis;}
}a[maxn];
int cnt = 0;
void dfs2(int now, int _f, int dis, int x, int cg)
{siz[now] = 1;a[++cnt] = (Node){dis, x};for(int i = head[now], v; i != -1; i = e[i].nxt){if(!out[v = e[i].to] && v != _f){dfs2(v, now, dis + e[i].w, now == cg ? v : x, cg);siz[now] += siz[v];}}
}int num[maxn], ans = 0;
void solve(int now)
{int cg = 0; cnt = 0;dfs1(now, 0, cg);dfs2(cg, 0, 0, 0, cg);sort(a + 1, a + cnt + 1);for(int i = head[cg]; i != -1; i = e[i].nxt)if(!out[e[i].to]) num[e[i].to] = 0;for(int i = 1; i <= cnt; ++i) num[a[i].bel]++;for(int i = 1, j = cnt; i <= j; ++i){num[a[i].bel]--;while(a[i].dis + a[j].dis > k && i <= j) num[a[j--].bel]--;if(i > j) break;ans += j - i - num[a[i].bel];}out[cg] = 1;for(int i = head[cg], v; i != -1; i = e[i].nxt)if(!out[v = e[i].to]) Siz = siz[v], solve(v);
}int main()
{Mem(head, -1);n = read();for(int i = 1; i < n; ++i){int x = read(), y = read(), w = read();addEdge(x, y, w); addEdge(y, x, w);}k = read();ans = 0; Siz = n;solve(1);write(ans), enter;return 0;
}