树的重心

找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心

void getroot(int x, int fa)
{
	son[x] = 1;
	int mx = 0;
	for (auto &to : g[x])
	{
		if (to == fa || vis[to])
			continue;
		getroot(to, x);
		son[x] += son[to];
		mx = max(mx, son[to]);
	}
	mx = max(mx, num - son[x]);
	if (mx < MX)
	{
		MX = mx;
		root = x;
	}
}

树的直径 （dfs）

先从图上任意一点，搜索整棵树，找到距离该点最远的点，再用距离该点最远的点搜索一次，即可得到树的直径。

void dfs(int x, int fa)
{
	for (int &to : g[x])
	{
		if (to != fa)
		{
			dis[to] = dis[x] + 1;
			dfs(to, x);
		}
	}		
}

int diameter()
{
	for (int i = 1; i <= n; i++)
		dis[i] = 0;
	dfs(1, -1);
	int mx = 0, st = 1;
	for (int i = 1; i <= n; i++)
		if (dis[i] > mx)
			mx = dis[i], st = i;
	for (int i = 1; i <= n; i++)
		dis[i] = 0;
	dfs(st, -1);
	mx = 0;
	for (int i = 1; i <= n; i++)
		mx = max(dis[i], mx);
	return mx;
}

最小生成树（MST）

Kruskal

稀疏图（边数少更有效率）

// n为点数m为边数 
struct DSU { // 并查集模板 
  int n; vector<int> dsu_fa;
  DSU(int _n) : n(_n) {
    for (int i = 0; i <= n; i++) {
      dsu_fa.push_back(i);
    }
  }
  int find(int x) {
    if (x != dsu_fa[x]) dsu_fa[x] = find(dsu_fa[x]);
    return dsu_fa[x];
  }
  bool merge(int x, int y) {
    x = find(x), y = find(y);
    dsu_fa[x] = y;
    return (x != y);
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
};

vector<pair<int,pair<int,int>>> e(m) // 存边(w,(u,v)) 

int kruskal() {
  DSU dsu(n);
  sort(e.begin(), e.end());
  int res = 0, cnt = 0;
  for (const auto &pi: e) {
    int u = pi.second.first, v = pi.second.second, w = pi.first;
    if (dsu.merge(u, v)) res += w, cnt++;
    if (cnt == n - 1) break;
  }
  return res;
}

Prim

稠密图（边数多更有效率）

int n, m, e[N][N]; 
ll mst[N], lowcost[N];//lowcost[i]：终点为i的最小花费，若lowcast[i] = 0，则表示i点已在当前所建的图中；mst[i]：终点为i的最小花费所对应的起点

int prim()
{
	ll sum = 0;
	for(int i = 2; i <= n; i++)
	{
		lowcost[i] = e[1][i];
	//	mst[i] = 1;
	}
	//mst[1] = 0;
	for(int i = 2; i <= n; i++)
	{
		int minid = -1;
		ll mi = inf;
		for(int j = 2; j <= n; j++)
		{
			if(lowcost[j] && lowcost[j] < mi)
			{
				minid = j;
				mi = lowcost[j];
			}
		}
		if(minid == -1)
			return inf;//图不联通返回inf 
		sum += lowcost[minid];
		lowcost[minid] = 0;
		for(int j = 2; j <= n; j++)
		{
			if(e[minid][j] < lowcost[j])
			{
				lowcost[j] = e[minid][j];
	//			mst[j] = minid;
			}
		}
	}
	return sum;
}

虚树

inline bool cmp(const int &a, const int &b){
    return dfn[a] < dfn[b];
}

void build()//二次排序
{
    sort(all(v), cmp);
    for(auto &it : v) t.push_back(it);
    for(int i = 1; i < v.size(); i++) t.push_back(LCA(v[i - 1], v[i]));//lca 和关键点放入，按dfn排序
    
    sort(all(t), cmp);
    t.erase(unique(all(t)), t.end());
    
    for(int i = 1; i < t.size(); i++)//lca 和 y 建边
    {
        int lca = LCA(t[i - 1], t[i]);
        int val = dis(lca, t[i]);
        G[lca].push_back({t[i], val});
        G[t[i]].push_back({lca, val});
    }
}