### 点分治

#### 树的直径

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
const int inf = 0x3f3f3f3f;
struct node {
int to,next;
int w;
}e[maxn];
int dis[maxn];
void addedge2(int u, int v ,int w) {
}
void init()
{
memset(dis,-inf, sizeof(dis));
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", &amp;n, &amp;m);
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &amp;u, &amp;v, &amp;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])最小的节点，即为重心。 • 转换成一遍搜索：在每次递归算一下儿子的最大值，每层算一下最大值的最小值。 //#include <bits/stdc++.h> #include <cstdio> #include <algorithm> #include <cstring> 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", &amp;n, &amp;m); for (int i = 0; i < m; i++) { int u, v, w; scanf("%d %d %d", &amp;u, &amp;v, &amp;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 模板题

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 20000 + 7;
const int inf = 0x3f3f3f3f;
int n;
int ans,ansIdx;
int son[maxn];
vector<int> 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 &amp;&amp; ansIdx > u)
ans = balance, ansIdx = u;
}
int main() {
int t; scanf("%d", &amp;t);
while (t--) {
scanf("%d", &amp;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", &amp;u, &amp;v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
printf("%d %d$n", ansIdx, ans); } return 0; }  ### 树的点分治 一种高效的用来解决树上的路径问题的算法思想 以树的重心为根转换无根树为有根树，这样可以保证分而治之的子树规模相当，且有任何一颗子树的大小都不超过原来树大小的一半。 最坏情况下树会退化成一条链普通枚举要上到$O(n^2+n)$ ### #POJ 1741 Tree 题意：给出一棵树，问有多少$pair(u,v)$使得$dis(u,v)$le k$

#### #Code

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = int (1e5 + 7);
const int inf = 0x3f3f3f3f;
struct node{
int to, next, w;
}e[maxn];
int n,k;
void addedge(int u, int v, int w) {
}
int vis[maxn];
struct Q_Q {
int N;
int subTMaxSize, CenterIdx;
int sz[maxn];
void dfs(int u, int fa) {
sz[u] = 1;
int res = 0; //此处不是平衡度，应是子树的大小，平衡度一个点为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];
res = max(res, sz[v] - 1);
}
res = max(res, N - sz[u]);
if (res < subTMaxSize)
subTMaxSize = res, CenterIdx = u;
}
int retCenter(int st) {
subTMaxSize = inf, CenterIdx = 0;
dfs(st, 0);
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; //更改u到虚根的距离
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);
//cal经过根u的路径数，在降维后要考虑选择的两个点都在根一侧
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); //除掉那些经过u的孩子h为根和v
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", &amp;n, &amp;k) != EOF, n + k) { init(); for (int i = 1; i < n; i++) { int u, v, w; scanf("%d%d%d", &amp;u, &amp;v, &amp;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;
}


This site uses Akismet to reduce spam. Learn how your comment data is processed.