14D - Two Paths

原题链接

这是一道基础的树形DP

题意：
给你一棵树，让你找两条不相交的路径，使得它们长度的乘积最大

思路：由于N只有\(200\)，因此直接枚举删掉哪一条边，然后分别求两棵树的直径\(d1, d2\)，然后对\(d1 * d2取max\)即可

代码如下

int h[N], e[M], ne[M], idx;
int n;
int res, l1, l2;
pii edge[N];

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

int dfs(int u, int fa, int type)
{
	int d1 = 0, d2 = 0, dist = 0;
	for(int i = h[u] ; ~i ; i = ne[i])
	{
		int j = e[i];
		if(j == fa) continue;
		int t = dfs(j, u, type) + 1;
		dist = max(dist, t);
		if(t > d1) d2 = d1, d1 = t;
		else if(t > d2) d2 = t;
	}
	if(type == 1)	l1 = max(l1, d1 + d2);
	else l2 = max(l2, d1 + d2);	
	
	return dist;
}

int main()
{
	IOS; 
	cin >> n;
	for(int i = 1 ; i < n ; i ++)
	{
		int a, b;
		cin >> a >> b;
		edge[i] = {a, b};
	}
	
	int l, r;
	for(int i = 1 ; i < n ; i ++)
	{
		memset(h, -1, sizeof h);
		l1 = l2 = idx = 0;
		l = edge[i].x, r = edge[i].y;
		for(int j = 1 ; j < n ; j ++)
		{
			if(i == j) continue;
			add(edge[j].x, edge[j].y);
			add(edge[j].y, edge[j].x);
		}
		
		dfs(l, -1, 1);
		dfs(r, -1, 2);
		res = max(res, l1 * l2);
	}
	
	cout << res << endl;
	
	return 0;
}

14D - Two Paths

原文：https://www.cnblogs.com/luoyicong/p/14668398.html