### 点分治

#### 树的直径

#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", &n, &m);
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &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])最小的节点，即为重心。
• 转换成一遍搜索：在每次递归算一下儿子的最大值，每层算一下最大值的最小值。

//#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 son[maxn];
void addedge2(int u, int v,int w) {
}
int n,m;
void init() {
memset(son, 0, sizeof(son));
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);
}
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 && 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

#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(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);
}
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;
}