题解 CF915F 【Imbalance Value of a Tree】
RainFestival
·
·
题解
我们首先显然的套路的，\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} I(i,j)
=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} \max(i,j)-\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} \min(i,j)
则我们可以分别求出两部分内容。
假设我们现在是边权，不是点权，那么我们可以使用并查集 \tt{dsu}。
具体这么做:
假设我们正在求最大值，我们可以算出每一条边的贡献 =w\times\sum\limits_{i=1}^{n}\sum\limits_{j=i}^{n} f(i,j)
我们考虑从小到大加入每一条边，设当前加入的边是 $(x,y,w)$ ,那么原先加入的每一条边都没有它大，所以我们合并 $x$ 与 $y$ 所在的连通块，**并加入** $w\times s_x\times s_y$ **的贡献**，其中 $s_i$ 表示 $i$ 所在的连通块大小。
为什么呢？
因为在 $x$ 的连通块内任选一个点 $p$ , 在 $y$ 的连通块内任选一个点 $q$ ,则 $p,q$ 之间的**唯一路径一定经过这一条边**，而这一条边是当前全图中最大的。
回到题目，现在我们是点权，所以我们可以**化点为边**，边 $(x,y)$ 的权值 $=\max(w_x,w_y)$ , 其中 $w_i$ 表示 $i$ 点点权。
最小值类似，只不过边权变成两点点权最小值，并且要从大到小加入每一条边。
代码如下：
```cpp
#include<cstdio>
#include<vector>
#include<algorithm>
struct edge
{
int x,y,m1,m2;
};
std::vector<int> a[1000005];
int n,fa[1000005],sz[1000005],val[1000005];
long long ans=0;
edge f[1000005];
int cmp1(edge x,edge y){return x.m2>y.m2;}
int cmp2(edge x,edge y){return x.m1<y.m1;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y)
{
int fx=find(x),fy=find(y);
fa[fx]=fy;sz[fy]=sz[fy]+sz[fx];
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&val[i]);
for (int i=1;i<n;i++)
{
scanf("%d%d",&f[i].x,&f[i].y);
f[i].m1=std::max(val[f[i].x],val[f[i].y]);
f[i].m2=std::min(val[f[i].x],val[f[i].y]);
}
std::sort(f+1,f+n,cmp1);
for (int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
for (int i=1;i<n;i++)
{
int x=f[i].x,y=f[i].y;
ans=ans-1ll*f[i].m2*sz[find(x)]*sz[find(y)];
merge(x,y);
}
std::sort(f+1,f+n,cmp2);
for (int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
for (int i=1;i<n;i++)
{
int x=f[i].x,y=f[i].y;
ans=ans+1ll*f[i].m1*sz[find(x)]*sz[find(y)];
merge(x,y);
}
printf("%lld\n",ans);
return 0;
}
```
然后就可以通过这一道题目了!
upd on 2020.8.10 修改了一些错误
upd on 2021.7.28 修改了一些错误，感谢 [U367991](https://www.luogu.com.cn/user/367991)