树的重心和直径

树的重心

性质：

1. 最大的子树最小
2. 找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡
3. 树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个距离和，他们的距离和一样，则这两个点都是重心（即重心可以有两个）
4. 把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上
5. 一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置
6. 一棵树最多有两个重心，且相邻。

思路：

1. 任选节点r为根节点做dfs，dfs的同时即更新所有的d(当前子树的大小)，以及最小的最大子树，注意当前子树的最大子树要考虑其父节点向上的树
2. 最后得到的包含最小的最大子树的节点就是重心了

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

int n, heart, mx, sz[maxn];
int head[maxn], to[maxn*2], nxt[maxn*2], tot;

inline void add_edge(int u, int v) {
    ++tot, to[tot]=v, nxt[tot]=head[u], head[u]=tot;
    ++tot, to[tot]=u, nxt[tot]=head[v], head[v]=tot;
}

void dfs(int u, int fa) {
    sz[u]=1; int mm=0;
    for(int i=head[u]; i; i=nxt[i]) {
        int v=to[i];
        if(v!=fa) {
            dfs(v,u);
            sz[u]+=sz[v];
            if(sz[v]>mm) mm=sz[v];
        }
    }
    if(n-sz[u]>mm) mm=n-sz[u];
    if(mm<mx) mx=mm, heart=u;
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    mx=inf, n=read();
    for(int i=1; i<n; ++i) add_edge(read(),read());
    dfs(1,0);
    printf("%d\n", heart);
}

树的直径

算法 $1$1：任选节点 $u$u做 $dfs$dfs，找到最远节点 $v$v；再从 $v$v做 $dfs$dfs，找到最远节点 $w$w，则 $v-w$v−w即为最长路径， $dis(v,w)$dis(v,w)即为树的直径。
适合于边权非负的情形，代码简单，因此先不给出算法 $1$1的代码QAQ

算法 $2$2：任选节点 $r$r作为根节点，求出最远距离 $f$f和次远距离 $s$s(在不同子树上)，则树的直径为 $f+s$f+s。
适用于所有情形

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int maxn=10100;
int n,ans;
int f[maxn],s[maxn];//f表示最长路，g表示次长路。
bool vis[maxn];
struct Node{
	int to,val;
	Node(int to=0,int val=0):to(to),val(val){}
};
vector <Node> G[maxn];
void DFS(int x){
	f[x]=s[x]=0;
	for(int i=0;i<G[x].size();i++){
		Node v=G[x][i];
		if (!vis[v.to]){
			vis[v.to]=true;
			DFS(v.to);//访问子节点。
			vis[v.to]=false;
			if(f[x]<f[v.to]+v.val){//如果发现了一条更长的路径，那么更新f[x]和g[x]。
				s[x]=f[x];//原来的f[x]变为次长路，新发现的记为最长路。
				f[x]=f[v.to]+v.val;
			}
			else if(s[x]<f[v.to]+v.val) s[x]=f[v.to]+v.val;//如果找到了一条比次长路更长的路径，那么更新g[x]。
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v,val;
		scanf("%d%d%d",&u,&v,&val);
		G[u].push_back(Node(v,val));
		G[v].push_back(Node(u,val));
	}
    int root=8; //随便选一个节点就行了
	vis[root]=true;
	DFS(root);
	printf("%d\n",f[root]+s[root]);
	return 0;
}