本文主要是介绍Educational Codeforces Round 36 (Rated for Div. 2) F. Imbalance Value of a Tree（并查集），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://codeforces.com/contest/915/problem/F
额挺傻逼的。求最小值相当于所有数取负后求最大值，然后就需要解决求最大值的问题。枚举每个点做的贡献，然后计数就好了，可以从小到大一个点一个点的向上加，然后用并查集维护整个树就好。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e6+5;
int fa[MAXN],sz[MAXN],head[MAXN];
bool book[MAXN];
void Init(int n)
{for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1,book[i]=false;
}
int Find(int x)
{if(x==fa[x])return x;else{fa[x]=Find(fa[x]);return fa[x];}
}
void Union(int x,int y)
{x=Find(x),y=Find(y);if(x!=y){sz[y]+=sz[x];fa[x]=y;}
}
int n,tot;
void init()
{tot=0;memset(head,-1,sizeof(head));
}
struct edge
{int v,nxt;
}E[MAXN*2];
struct node
{int id,v;bool operator <(const node &o)const{return v<o.v;}
}a[MAXN];
void addedge(int u,int v)
{E[tot].v=v;E[tot].nxt=head[u];head[u]=tot++;E[tot].v=u;E[tot].nxt=head[v];head[v]=tot++;
}
inline char nc()
{static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void rea(int &x)
{char c=nc();x=0;for(;c>'9'||c<'0';c=nc());for(;c>='0'&&c<='9';x=x*10+c-'0',c=nc());
}
ll cal()
{ll ret=0;sort(a+1,a+1+n);Init(n);for(int i=1;i<=n;i++){int id=a[i].id;book[id]=true;ret+=a[i].v;for(int j=head[id];~j;j=E[j].nxt){int v=E[j].v;if(book[v]){v=Find(v);ret+=1LL*a[i].v*sz[Find(id)]*sz[v];Union(id,v);}}}return ret;
}
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);init();rea(n);for(int i=1;i<=n;i++)rea(a[i].v),a[i].id=i;for(int i=1;i<n;i++){int u,v;rea(u);rea(v);addedge(u,v);}ll ans=0;ans+=cal();for(int i=1;i<=n;i++)a[i].v=-a[i].v;ans+=cal();printf("%lld\n",ans);return 0;
}
这篇关于Educational Codeforces Round 36 (Rated for Div. 2) F. Imbalance Value of a Tree（并查集）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
