[BZOJ2870]最长道路tree

给定一棵N个点的树，求树上一条链使得链的长度乘链上所有点中的最小权值所得的积最大。

其中链长度定义为链上点的个数。

有点分治/边分治做法，懒得写了。本题用并查集即可轻松水过

将点按照权值从大到小排序依次加点，维护每个点所在连通块的直径端点，合并的时候就是C(4,2)=6选一下即可

然后将直径*这个点点权取个max

如果直径不过这个点肿么办？那么这个直径上点权最小值一定大于这个点，而肯定会被统计到的（即不存在大于实际答案的不合法答案）

105行一遍AC。

#include <bits/stdc++.h>
using namespace std;

struct edge
{
	int v, ne;
} a[100010];

int h[50010], tmp;
int n, val[50010], fa[50010][17], depth[50010];
int ds[50010], d1[50010], d2[50010];
int order[50010];
bool vis[50010];

void add(int x, int y)
{
	a[++tmp] = (edge){y, h[x]};
	h[x] = tmp;
}

int getf(int x)
{
	return ds[x] == x ? x : ds[x] = getf(ds[x]);
}

bool fuck(int x, int y)
{
	return val[x] > val[y];
}

int lca(int x, int y)
{
	if (depth[x] < depth[y])
		swap(x, y);
	int dist = depth[x] - depth[y];
	for (int i = 16; i >= 0; i--)
		if (dist & (1 << i))
			x = fa[x][i];
	if (x == y)
		return x;
	for (int i = 16; i >= 0; i--)
		if (fa[x][i] != fa[y][i])
			x = fa[x][i], y = fa[y][i];
	return fa[x][0];
}

int dis(int x, int y)
{
	return depth[x] + depth[y] - 2 * depth[lca(x, y)];
}

int addedge(int x, int y)
{
	x = getf(x), y = getf(y);
	if (x == y)
		printf("cnm!
");
	ds[x] = y;
	int p1 = d1[x], p2 = d2[x], p3 = d1[y], p4 = d2[y];
	int maxn = -233, fuck;
	if ((fuck = dis(p1, p2)) > maxn) d1[y] = p1, d2[y] = p2, maxn = fuck;
	if ((fuck = dis(p1, p3)) > maxn) d1[y] = p1, d2[y] = p3, maxn = fuck;
	if ((fuck = dis(p1, p4)) > maxn) d1[y] = p1, d2[y] = p4, maxn = fuck;
	if ((fuck = dis(p2, p3)) > maxn) d1[y] = p2, d2[y] = p3, maxn = fuck;
	if ((fuck = dis(p2, p4)) > maxn) d1[y] = p2, d2[y] = p4, maxn = fuck;
	if ((fuck = dis(p3, p4)) > maxn) d1[y] = p3, d2[y] = p4, maxn = fuck;
	return dis(d1[y], d2[y]) + 1;
}

void dfs(int x)
{
	for (int i = h[x]; i != 0; i = a[i].ne)
		if (fa[x][0] != a[i].v)
		{
			fa[a[i].v][0] = x;
			depth[a[i].v] = depth[x] + 1;
			dfs(a[i].v);
		}
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &val[i]);
	for (int x, y, i = 1; i < n; i++)
		scanf("%d%d", &x, &y), add(x, y), add(y, x);
	dfs(1);
	for (int j = 1; j <= 16; j++)
		for (int i = 1; i <= n; i++)
			fa[i][j] = fa[fa[i][j - 1]][j - 1];
	for (int i = 1; i <= n; i++)
		ds[i] = d1[i] = d2[i] = order[i] = i;
	sort(order + 1, order + 1 + n, fuck);
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		int x = order[i];
		vis[x] = true;
		for (int j = h[x]; j != 0; j = a[j].ne)
			if (vis[a[j].v] == true)
				ans = max(ans, addedge(x, a[j].v) * val[x]);
	}
	printf("%d
", ans);
	return 0;
}

真的懒得写点分治和边分治了

[BZOJ2870]最长道路tree

相关推荐