# 点分治

## 树的直径

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63  #include using namespace std; const int maxn = 1e5 + 7; const int inf = 0x3f3f3f3f; struct node { int to,next; int w; }e[maxn]; int ecnt, head[maxn]; int dis[maxn]; void addedge2(int u, int v ,int w) { e[ecnt] = node{u, head[v], w}; head[v] = ecnt++; e[ecnt] = node{v, head[u], w}; head[u] = ecnt++; } void init() { memset(dis,-inf, sizeof(dis)); memset(head, -1, sizeof(head)); ecnt = 0; } void dfs(int u, int fa, int d) { //传入当前深入的距离便于回溯 for (int i = head[u]; ~i; i = e[i].next) { int v = e[i].to, w = e[i].w; if (v == fa) continue; dis[v] = w + d; dfs(v, u, dis[v]); } } int main() { int n, m; init(); scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); addedge2(u, v, w); } int st = 1; dfs(st, -1, 0); int idx = -1, MAX = -inf; for (int i = 1; i <= n; i++) { if (dis[i] > MAX) idx = i, MAX = dis[i]; } dis[idx] = 0, MAX = -1; dfs(idx, -1, 0); for (int i = 1; i <= n; i++)MAX = max(MAX, dis[i]); return !printf("%d\n", MAX); } / * Sample input 7 6 1 2 3 2 3 4 2 4 2 4 5 5 4 6 1 5 7 3 Sample output 14 * / 

## 树的重心

• 两遍搜索，第一次随便定一个根，搜出每个孩子的子节点son[u],第二遍搜出使得max(son[u],n-1-son[u])最小的节点，即为重心。
• 转换成一遍搜索：在每次递归算一下儿子的最大值，每层算一下最大值的最小值。
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67  //#include #include #include #include using namespace std; const int maxn = 1e5 + 7; const int inf = 0x3f3f3f3f; struct node { int to, next; int w; }e[maxn]; int ecnt, head[maxn]; int son[maxn]; void addedge2(int u, int v,int w) { e[ecnt] = node{u, head[v], w}; head[v] = ecnt++; e[ecnt] = node{v, head[u]}, w; head[u] = ecnt++; } int n,m; void init() { memset(son, 0, sizeof(son)); memset(head, -1, sizeof(head)); ecnt = 0; } int siz, ans; bool vis[maxn]; void dfs1(int u, int fa) { son[u] = 1; int res = -inf; for (int i = head[u]; ~i; i = e[i].next) { int v = e[i].to; if (v == fa || vis[v]) continue; dfs1(v, u); son[u] += son[v]; res = max(res, son[v] - 1); } res = max(res, n - son[u]); if (res < siz) { ans = u; siz = res; } } int main() { init(); scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) { int u, v, w; scanf("%d %d %d", &u, &v, &w); addedge2(u, v, w); } int st = 1; memset(vis, 0, sizeof(vis)); ans = 0, siz = inf; dfs1(st, 0); printf("%d\n", ans); } /*Sample input 7 6 1 2 3 2 3 4 2 4 2 4 5 5 4 6 1 5 7 3 Sample output 4 */ 

### POJ 1655 模板题

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44  #include #include #include #include using namespace std; const int maxn = 20000 + 7; const int inf = 0x3f3f3f3f; int n; int ans,ansIdx; int son[maxn]; vector g[maxn]; void dfs(int u, int fa) { int balance = 0; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (v == fa) continue; dfs(v, u); son[u] += son[v] + 1; balance = max(balance, son[v] + 1); } balance = max(balance, n - son[u] - 1); if (balance < ans || balance == ans && ansIdx > u) ans = balance, ansIdx = u; } int main() { int t; scanf("%d", &t); while (t--) { scanf("%d", &n); for (int i = 0; i <= n; i++) { son[i] = 0; g[i].clear(); } ans = inf, ansIdx = 0; for (int i = 1; i <= n - 1; i++) { int u, v; scanf("%d %d", &u, &v); g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); printf("%d %d\n", ansIdx, ans); } return 0; } 

## 树的点分治

### POJ 1741 Tree

#### Code

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109  #include #include #include using namespace std; const int maxn = 1e5 + 7; const int inf = 0x3f3f3f3f; struct node{ int to, next, w; }e[maxn]; int head[maxn], ecnt; int n,k; void addedge(int u, int v, int w) { e[ecnt] = node{v, head[u], w}; head[u] = ecnt++; } int vis[maxn]; struct Q_Q { int N; int subTMaxSize, CenterIdx; int sz[maxn]; void dfs(int u, int fa) { sz[u] = 1; int balance = 0; for (int i = head[u]; ~i; i = e[i].next) { int v = e[i].to; if (v == fa || vis[v]) continue; dfs(v, u); sz[u] += sz[v]; balance = max(balance, sz[v] - 1); } balance = max(balance, N - sz[u]); if (balance < subTMaxSize) subTMaxSize = balance, CenterIdx = u; } int retCenter(int st) { subTMaxSize = inf, CenterIdx = 0; dfs(st, -1); return CenterIdx; } }; Q_Q X_X; int data[maxn], Len; int dis[maxn]; int ANS; void dfs(int u, int fa) { data[++Len] = dis[u]; for (int i = head[u]; ~i; i = e[i].next) { int v = e[i].to; int w = e[i].w; if (v == fa || vis[v]) continue; dis[v] = dis[u] + w; dfs(v, u); } } int cal(int u, int now) { dis[u] = now; Len = 0; dfs(u, 0); sort(data + 1, data + Len + 1); int res = 0; int l = 1, r = Len; while (l < r) { if (data[r] + data[l] <= k) res += r - l++; else r--; } return res; } void solve(int u) { ANS += cal(u, 0); vis[u] = 1; for (int i = head[u]; ~i; i = e[i].next) { int v = e[i].to; int w = e[i].w; if (vis[v]) continue; ANS -= cal(v, w); X_X.N = X_X.sz[v]; // printf("Center root : %d\n",X_X.retCenter(v)); solve(X_X.retCenter(v)); } } void init(){ ANS = 0; ecnt = 0; memset(head, -1, sizeof(head)); memset(vis, 0, sizeof(vis)); } int main() { while (scanf("%d%d", &n, &k) != EOF, n + k) { init(); for (int i = 1; i < n; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); addedge(u, v, w); addedge(v, u, w); } X_X.N = n; int st = 1; int root = X_X.retCenter(st); #ifndef ONLINE_JUDGE printf("Root = %d\n", root); #endif solve(root); printf("%d\n", ANS); } return 0; } 

to be continue…