树形网络某节点到其他节点的最远距离

[eiclpy]

#include <cstdio>
#include <cstring>
inline int max(int x, int y) { return x > y ? x : y; }
#define MAXN 100000
struct TreeNetwork
{
	struct Edge
	{
		int to, len, next, mxd;
	} edges[MAXN];
	typedef int array[MAXN];
	array head;
	array fa, mxdeep;
	array big1, bip1, big2;
	void addEdge(int u, int v, int w)
	{
		static int tot = 1;
		edges[++tot] = (Edge){v, w, head[u], 0};
		head[u] = tot;
		edges[++tot] = (Edge){u, w, head[v], 0};
		head[v] = tot;
	}
	void dfs1(int x)
	{
		for (int p = head[x]; p; p = edges[p].next)
		{
			int to = edges[p].to;
			if (to == fa[x])
				continue;
			fa[to] = x;
			dfs1(to);
			edges[p].mxd = mxdeep[to] + edges[p].len;
			mxdeep[x] = max(mxdeep[x], edges[p].mxd);
		}
	}
	void dfs2(int x)
	{
		int md, to;
		for (int p = head[x]; p; p = edges[p].next)
		{
			to = edges[p].to;
			md = edges[p].mxd;
			if (md > big2[x])
				if (md > big1[x])
					big2[x] = big1[x], big1[x] = md, bip1[x] = to;
				else
					big2[x] = md;
		}
		for (int p = head[x]; p; p = edges[p].next)
		{
			to = edges[p].to;
			edges[p ^ 1].mxd = to != bip1[x] ? big1[x] + edges[p].len : big2[x] + edges[p].len;
			if (to == fa[x])
				continue;
			dfs2(to);
		}
	}
	void solve()
	{
		fa[1] = MAXN;
		dfs1(1);
		dfs2(1);
	}
};
TreeNetwork net;
int main()
{
	memset(&net, 0, sizeof(TreeNetwork));
	int n;
	scanf("%d", &n); //n个点
	for (int i = 1; i < n; ++i)
	{
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w); //点u点v间有一条长w的边
		net.addEdge(u, v, w);
	}
	net.solve();
	for (int i = 1; i <= n; ++i)
		printf("%d %d\n", i, net.big1[i]); //到i最远的节点的距离
	return 0;
}