前言：

虽然很多人和我想法一样，但我还是不要脸地写了这题解

题目：

链接

大意：

在一棵树上取一条最长链以及它所连接的结点总共的结点个数

思路:

取链：

用树形\(DP\)就可以轻而易举的解决这个问题：

\(f_x\)表示以\(x\)为根节点的树的深度

转移方程：

\[f_x=max\{f_y + 1 \} (y\in son(x))
\]

那么以\(x\)为根节点的树的最长链就是\(f_x\)加上次大的子树深度，下方代码区以\(ans\)来表示。

代码：

void dp(int x, int root)

{

	f[x] = 1;

	int maxn = 0, lown = 0; //最大 与 次大

	for (int i = head[x]; i; i = next[i])

	{

		int y = to[i];

		if (y == root) continue;

		dp(y, x);

		if(f[y] > lown)

		{

			if(f[y] > maxn) lown = maxn, maxn = f[y];

			else lown = f[y];

		}

		f[x] = max(f[x], f[y] + 1);

	}

	ans = max(ans, f[x] + lown);

}

链所连接的结点：

也就是说只用加上周边的结点就可以了，不用再递归下去。

那我们先在\(\texttt{main()}\)里记录每个节点的儿子个数

然后递归就可以直接加上去就可以惹！

代码：

void dp(int x, int root)

{

	f[x] = 1;

	int num = 0;

	int maxn = 0, lown = 0;

	for (int i = head[x]; i; i = next[i])

	{

		int y = to[i];

		if (y == root) continue;

		dp(y, x);

		if(f[y] > lown)

		{

			if(f[y] > maxn) lown = maxn, maxn = f[y];

			else lown = f[y];

		}

		f[x] = max(f[x], f[y] + son[x] - 1);  //减1是因为父结点也算进去了

	}

	ans = max(ans, lown + maxn + son[x] - 1);

}

int main()

{

	scanf("%d%d", &n, &m);

	for (int i = 1; i <= m; i++)

	{

		int x, y;

		scanf("%d%d", &x, &y);

		ADD(x, y);

		ADD(y, x);

		son[x] ++, son[y] ++;

	}

	dp(1, 0);

	printf("%d", ans);

    return 0;

}

祝\(CSP.rp++\)

巴特西

【Luogu P3174 】[HAOI2009]毛毛虫

前言：

题目：

大意：

思路:

取链：

代码：

链所连接的结点：

代码：

最新文章

热门文章