并查集的一道比较考想法的题
题意：给你n个点，接着给你n-1条边形成一颗生成树，每条边都有一个权值。求的是以一个点作为特殊点，并求出从此点出发到其他每个点的条件边权的总和最大，条件边权就是：起点到终点经过的权值的最小值。
如果按照最原始的想法来做的话就是枚举每个点作为特殊点，离线dfs再遍历到每个点来计算条件边权总和，最后求一个最大值即可。但是此题点数有20万显然超时，接着想了一下是否可以枚举每个点后，使用数据结构或模拟dp（使用之前的条件边权总和）优化成为log2n，结果并没有什么想法。然而如果我不枚举点，直接贪心来做的话就可以解决问题了。我们可以想到每次加边的时候，权值必须小于那些（出现过的任意一对点），才会影响那些的权值，因此可以想到排序权值。
我的想法是这样的：我们离线操作从大到小排序权值，使用并查集把祖先节点看做特殊点，接着每次加边的时候更新祖先（合并操作），更新时需要决定祖先是哪个。我们知道更新后的祖先是要保证树上的每个点到其的条件边权的总和最大，而两棵树的祖先之一才可能出现这种情况（满足后效性），所以我们只需要需要比较两个祖先。此时我们可以想到，如果A树的祖先为更新后的祖先，A树上的条件边权总和并不会变，而B树上的每个点的条件边权则会变成现在加边的权值（我们从大到小排的序），所以我们只需再祖先上的记录两个权值：一个是树上总点数num，一个此树条件边权的总和manx。
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<stdlib.h> #include<iostream> #include<algorithm> using namespace std; #define eps 1E-8 /*注意可能会有输出-0.000*/ #define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型 #define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化 #define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0 #define mul(a,b) (a<<b) #define dir(a,b) (a>>b) typedef long long ll; typedef unsigned long long ull; const int Inf=1<<28; const double Pi=acos(-1.0); const int Mod=1e9+7; const int Max=200010; int fat[Max],num[Max]; ll manx[Max]; struct node { int xx1,yy1,val; }tow[Max]; void Init(int n) { for(int i=0;i<=n;i++) { fat[i]=i; num[i]=1; manx[i]=0ll; } return; } bool cmp(struct node p1,struct node p2) { return p1.val>p2.val; } int Find(int x) { if(x==fat[x]) return fat[x]; return fat[x]=Find(fat[x]); } void Union(int x,int y,int z) { int x1=Find(x); int y1=Find(y); if((ll)num[x1]*z+manx[y1]>(ll)num[y1]*z+manx[x1])//哪边为根权值和最大 { fat[x1]=y1; manx[y1]+=(ll)num[x1]*z; num[y1]+=num[x1]; } else { fat[y1]=x1; manx[x1]+=(ll)num[y1]*z; num[x1]+=num[y1]; } return; } int main() { int n; while(~scanf("%d",&n)) { Init(n); for(int i=0;i<n-1;i++) scanf("%d %d %d",&tow[i].xx1,&tow[i].yy1,&tow[i].val); sort(tow,tow+n-1,cmp);//点与点之间的权值为所形成路径的最小权值，最大的权值最先找祖先保证合并时最小权值一定是当前权值 for(int i=0;i<n-1;i++) Union(tow[i].xx1,tow[i].yy1,tow[i].val); printf("%lld ",manx[Find(1)]);//形成一棵树，答案在根节点 } return 0; }