503 最长路径

itdef / 2024-10-10 / 原文

// 503 最长路径.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
http://oj.daimayuan.top/course/5/problem/226

有一棵 n个节点的树，节点编号从 1 到 n。
对于每个节点，请求出经过它的长度最长的简单路径有多长。

定义一条路径的长度为这条路径上经过了多少条边。

输入格式
第一行一个整数 n 表示节点数。

接下来 n−1 行，每行两个整数 x,y 表示 x号节点和 y 号节点之间有一条边。

数据保证读入的是一棵树。

输出格式
输出共 n 行，第 i 行一个整数表示经过 i 号节点的长度最长的简单路径有多长。

样例输入
5
1 2
1 5
2 3
2 4
样例输出
3
3
3
3
3
数据规模
对于所有数据，保证 2≤n≤105,1≤x,y≤n。
*/

#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;
int h[N], e[2 * N], ne[2 * N], idx;
int n, f[100010][2][2], v[100010];


void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void up(int u, int fa) {
	for (int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i]; 
		if (j == fa) continue;
		up(j,u);
		if (f[j][0][0] + 1 > f[u][0][0]) {
			f[u][1][0] = f[u][0][0], f[u][1][1] = f[u][0][1], f[u][0][0] = f[j][0][0] + 1, f[u][0][1] = j;
		}
		else {
			if (f[j][0][0] + 1 > f[u][1][0])
				f[u][1][0] = f[j][0][0] + 1, f[u][1][1] = j;
		}
	}
}

void down(int u, int fa) {
	for(int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i];
		if (j == fa) continue;
		if (f[u][0][1] == j) {
			if (v[u] > f[u][1][0])
				v[j] = v[u] + 1;
			else
				v[j] = f[u][1][0] + 1;
		}
		else {
			v[j] = max(f[u][0][0], v[u]) + 1;
		}
		down(j, u);
	}
}

int main() {
	memset(h, -1, sizeof h);
	//l = 0;
	cin >> n;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		add(x, y);
		add(y, x);
	}
	up(1, -1);
	down(1, -1);
	 
	for (int i = 1; i <= n; i++)
		cout << f[i][0][0] + f[i][1][0] + v[i] - min(min(f[i][0][0], f[i][1][0]), v[i]) << endl;
}