如何求出经过节点x的最长链的长度f[x]
  • 板块学术版
  • 楼主Kobe303
  • 当前回复8
  • 已保存回复8
  • 发布时间2022/2/27 14:02
  • 上次更新2023/10/28 07:36:56
查看原帖
如何求出经过节点x的最长链的长度f[x]
292300
Kobe303楼主2022/2/27 14:02
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n;
int head[N], ver[N*2], nxt[N*2], cnt;
int d[N], f[N], mx;

void add(int u, int v) {
	ver[++cnt] = v, nxt[cnt] = head[u], head[u] = cnt;
}

void dp(int u, int fa) {
	for (int i = head[u]; i; i = nxt[i]) {
		int v = ver[i];
		if (v == fa) continue;
		dp(v, u);
		f[u] = max(f[u], d[u] + d[v] + 1);
		d[u] = max(d[u], d[v] + 1);
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; ++i) {
		int u, v; scanf("%d%d", &u, &v);
		add(u, v), add(v, u);
	}
	dp(1, 0);
	for (int i = 1; i <= n; ++i) printf("%d ", f[i]);
	return 0;
}

这是菜鸡的代码,但是不对 /kk

2022/2/27 14:02
加载中...