题目

现在有一棵n个点的无向树，每个点的编号在1-n之间，求出每个点所在的最长路。

思路

换根 \(dp\)，这里只是记下怎么打

\(Code\)

#include<cstdio>

#include<iostream>

using namespace std;

const int N = 1e5;

int n , h[N + 5] , tot , f1[N + 5] , f2[N + 5] , g1[N + 5] , g2[N + 5];

struct edge{

	int nxt , to , w;

}e[2 * N + 5];

inline void add(int u , int v , int w)

{

	e[++tot].to = v;

	e[tot].w = w;

	e[tot].nxt = h[u];

	h[u] = tot;

}

inline void dfs1(int u , int fa)

{

	for(register int i = h[u]; i; i = e[i].nxt)

	{

		int v = e[i].to;

		if (v == fa) continue;

		dfs1(v , u);

		if (f1[v] + e[i].w > f1[u]) f2[u] = f1[u] , f1[u] = f1[v] + e[i].w;

		else if (f1[v] + e[i].w > f2[u]) f2[u] = f1[v] + e[i].w;

	}

}

inline void dfs2(int u , int fa)

{

	for(register int i = h[u]; i; i = e[i].nxt)

	{

		int v = e[i].to;

		if (v == fa) continue;

		if (f1[v] + e[i].w == g1[u])

		{

			if (g2[u] + e[i].w > f1[v]) g1[v] = g2[u] + e[i].w , g2[v] = f1[v];

			else g2[v] = g2[u] + e[i].w , g1[v] = f1[v];

		}

		else {

			if (g1[u] + e[i].w > f1[v]) g1[v] = g1[u] + e[i].w , g2[v] = f1[v];

			else g2[v] = g1[u] + e[i].w , g1[v] = f1[v];

		}

		g1[v] = max(g1[v] , f1[v]) , g2[v] = max(g2[v] , f2[v]);

		dfs2(v , u);

	}

}

int main()

{

	freopen("tree.in" , "r" , stdin);

	freopen("tree.out" , "w" , stdout);

	scanf("%d" , &n);

	int u , v , w;

	for(register int i = 1; i < n; i++)

	{

		scanf("%d%d%d" , &u , &v , &w);

		add(u , v , w) , add(v , u , w);

	}

	dfs1(1 , 0);

	g1[1] = f1[1] , g2[1] = f2[1];

	dfs2(1 , 0);

	for(register int i = 1; i <= n; i++) printf("%d\n" , g1[i] + g2[i]);

}

巴特西

JZOJ 4279. 【NOIP2015模拟10.29B组】树上路径

题目

思路

\(Code\)

最新文章

热门文章