Codeforces Round #14 D. Two Paths(求树上两条不相交的路径的乘积最大值)

题目链接：

http://codeforces.com/problemset/problem/14/D

思路：直接枚举每一天路径的两端，然后求以每一端为树根的树上最长路径，然后相乘就可以了。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#define REP(i, a, b) for (int i = (a); i < (b); ++i)

#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)

using namespace std;

const int MAX_N = (200 + 20);

int N, ed, maxlen, ans, dp[MAX_N], pre[MAX_N];

vector<int > g[MAX_N];

void dfs(int u, int fa, int len, int limit)

{

	dp[u] = len;

	pre[u] = fa;

	REP(i, 0, (int)g[u].size()) {

		int v = g[u][i];

		if (v != fa && v != limit) dfs(v, u, len + 1, limit);

	}

}

int gao(int u, int v)

{

	memset(dp, 0, sizeof(dp));

	dfs(u, -1, 0, v);

	maxlen = 0; ed = u;

	FOR(i, 1, N) if (dp[i] > maxlen) maxlen = dp[i], ed = i;

	dfs(ed, -1, 0, v);

	maxlen = 0;

	FOR(i, 1, N) if (dp[i] > maxlen) maxlen = dp[i], ed = i;

	maxlen = 0;

	while (pre[ed] != -1) ed = pre[ed], ++maxlen;

	return maxlen;

}

int main()

{

	cin >> N;

	REP(i, 1, N) {

		int u, v; cin >> u >> v;

		g[u].push_back(v);

		g[v].push_back(u);

	}

	ans = 0;

	FOR(i, 1, N) {

		REP(j, 0, (int)g[i].size()) {

			int l = gao(i, g[i][j]);

			int r = gao(g[i][j], i);

			ans = max(ans, l * r);

		}

	}

	cout << ans << endl;

	return 0;

}

巴特西

Codeforces Round #14 D. Two Paths(求树上两条不相交的路径的乘积最大值)

最新文章

热门文章