求树的的直径

diameter.cpp

// 两遍DFS,直径上的点保存在trace中

const int maxn = 1e5 + 5;

typedef pair<int, int> PII;

int n, pre[maxn], dis[maxn];
vector<PII> g[maxn];

void dfs(int x, int fa) {
    pre[x] = fa;
	for (PII e : g[x]) {
		if (e.first == fa) continue;
		dis[e.first] = dis[x] + e.second;
		dfs(e.first, x);
	}
}

void calcDiameter() {
	int st = 1, ed = 1;
	vector<int> trace;
	dfs(1, dis[1] = 0);
	for (int i = 1; i <= n; i++) {
		if (dis[i] > dis[st]) st = i;
	}
	dfs(st, dis[st] = 0);
	for (int i = 1; i <= n; i++) {
		if (dis[i] > dis[ed]) ed = i;
	}
	while (ed != 0) {
		trace.push_back(ed);
		ed = pre[ed];
	}
}