[CSP-S模拟测试]:影子（并查集+LCA）

题目描述

一个人有很多的影子，新的旧的，他们不断消失重来。学者的影子在他苍白色的精神图景里成为了$n$个黑色的点，他们伸长的触手交叉形成了一颗黑色的树。假使每个影子点拥有一个权值$d_i$，黑色的树边也有一个权值$w_i$，对于一条黑色树的路径，令路径上所有影子点权值$d_i$的最小值为${min}_d$，路径上所有树边权值$w_i$的总和为$sum_w$，则该条路径的总权值为${min}_d\times sum_w$。路径的起点和终点可以是黑色树中的任意影子点，且路径中不能出现重复的影子点。
现在学者需要知道这棵黑色树里所有路径总权值中的最大值为多少

输入格式

第一行输入一个整数$T$，表示数据组数
每组数据第一行一个正整数$n$，表示影子点总数
之后$n$个整数，表示每个影子点的权值
之后$n-1$行，每行三个整数$u,v,w$表示一条连接$u,v$且权值为$w$的树边。数据保证不会出现重边，且一定构成树结构

输出格式

一共$T$行，表示当前这组数据的答案

样例

样例输入：

1
3
1 2 3
1 2 1
1 3 2

样例输出：

数据范围与提示

样例解释：

总权值最大的路径是$2\rightarrow 1\rightarrow 3$，${min}_d$为$min(1,2,3)=1$，${sum}_w$为$sum(1,2)=3$，因此答案为$1\times 3=3$。

数据范围：

对于$100\%$的数据$1\leqslant T\leqslant 10,1\leqslant n\leqslant {10}^5,1\leqslant d_i\leqslant {10}^9,1\leqslant u,v\leqslant n,1\leqslant w_i\leqslant {10}^9$
其中$35\%$的数据$1\leqslant n\leqslant 100$
其中最多有$50\%$的数据保证${10}^4\leqslant n\leqslant {10}^5$

题解

再一次没有打正解，显然正解是点分治。

然而我用的是比较玄学的并查集。

首先，将所有的点权从大到小排序，于将当前点和与其相连的所有点依次合并到一个集合中。

并查集维护当前集合中的最长路径长度和对应的两个端点。

保证当前这个点是并查集中最大的点，这样它肯定对$min_d$没有贡献。

那么，合并两个集合后集合的最长路分为两种情况：

　　$\alpha.$其中一个集合的最长路。

　　$\beta.$两个集合的最长路的端点相互连接。

这里就需要用到$LCA$了。

每次合并并查集之后用当前点的权值乘以最长路的总长度来更新最优结果即可。即使这个点不在当前合并后的集合的最长路上也是没有问题的，因为如果这样的话，必然已经在之前得到了对应的结果，这次合并不会对最终结果产生影响。

时间复杂度：$\Theta(n\log n)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

struct rec{int nxt,to,w;}e[200001];

int head[100001],cnt;

int n;

int f[100001],lft[100001],rht[100001],rk[100001];

int fa[100001][21],depth[100001];

long long dis[100001],len[100001];

pair<int,int> d[100001];

long long ans;

void pre_work()

{

	memset(len,0,sizeof(len));

	memset(head,0,sizeof(head));

	memset(depth,0,sizeof(depth));

	ans=cnt=0;

	for(int i=1;i<=n;i++)f[i]=lft[i]=rht[i]=i;

}

void add(int x,int y,int w)

{

	e[++cnt].nxt=head[x];

	e[cnt].to=y;

	e[cnt].w=w;

	head[x]=cnt;

}

int find(int x){return x==f[x]?x:f[x]=find(f[x]);}

void dfs(int x)

{

	for(int i=head[x];i;i=e[i].nxt)

	{

		if(depth[e[i].to])continue;

		depth[e[i].to]=depth[x]+1;

		fa[e[i].to][0]=x;

		for(int j=1;j<=20;j++)

			fa[e[i].to][j]=fa[fa[e[i].to][j-1]][j-1];

		dis[e[i].to]=dis[x]+e[i].w;

		dfs(e[i].to);

	}

}

int LCA(int x,int y)

{

	int minn=1<<30;

	if(depth[x]>depth[y])swap(x,y);

	for(int i=20;~i;i--)

		if(depth[fa[y][i]]>=depth[x])

			y=fa[y][i];

	if(x==y)return x;

	for(int i=20;~i;i--)

		if(fa[x][i]!=fa[y][i])

		{

			x=fa[x][i];

			y=fa[y][i];

		}

	return fa[x][0];

}

long long get_dis(int x,int y){return dis[x]+dis[y]-(dis[LCA(x,y)]<<1);}

int main()

{

	int T;scanf("%d",&T);

	while(T--)

	{

		scanf("%d",&n);

		pre_work();

		for(int i=1;i<=n;i++)

		{

			int x;scanf("%d",&x);

			d[i]=make_pair(x,i);

		}

		sort(d+1,d+n+1,greater<pair<int,int> >());

		for(int i=1;i<n;i++)

		{

			int u,v,w;

			scanf("%d%d%d",&u,&v,&w);

			add(u,v,w);

			add(v,u,w);

		}

		depth[1]=1;

		dfs(1);

		for(int i=1;i<=n;i++)rk[d[i].second]=i;

		for(int i=1;i<=n;i++)

		{

			for(int j=head[d[i].second];j;j=e[j].nxt)

			{

				int to=find(e[j].to);

				if(rk[d[i].second]<rk[to])continue;

				len[0]=len[d[i].second],lft[0]=lft[d[i].second],rht[0]=rht[d[i].second];

				if(len[to]>len[0]){len[0]=len[to];lft[0]=lft[to];rht[0]=rht[to];}

				if((dis[0]=get_dis(lft[d[i].second],lft[to]))>len[0]){len[0]=dis[0];lft[0]=lft[d[i].second];rht[0]=lft[to];}

				if((dis[0]=get_dis(rht[d[i].second],rht[to]))>len[0]){len[0]=dis[0];lft[0]=rht[d[i].second];rht[0]=rht[to];}

				if((dis[0]=get_dis(lft[d[i].second],rht[to]))>len[0]){len[0]=dis[0];lft[0]=lft[d[i].second];rht[0]=rht[to];}

				if((dis[0]=get_dis(rht[d[i].second],lft[to]))>len[0]){len[0]=dis[0];lft[0]=rht[d[i].second];rht[0]=lft[to];}

				f[to]=d[i].second;lft[d[i].second]=lft[0];rht[d[i].second]=rht[0];len[d[i].second]=len[0];

			}

			ans=max(ans,len[d[i].second]*d[i].first);

		}

		printf("%lld\n",ans);

	}

	return 0;

}

rp++

巴特西