免费b站软件推广网站_步骤怎么写_站内seo和站外seo区别_西安竞价推广托管

题面

题面翻译

给定一棵树，每个顶点都被写上了一个数，第 $i$ 个顶点写上的数是 $a_i$。定义一个函数 $I(x,y)$ 表示从顶点 $x$ 到 $y$ 的简单路径上 $a_i$ 的最大值和最小值的差。

你要求出 ${\sum }_{i=1}^n{\sum }_{j=i}^{n}I(i,j)$。

输入格式：

第一行一个正整数 $n(1\le n\le 10^6)$，表示树上节点个数。

第二行 $n$ 个正整数 $a_1,a_2,\cdots ,a_n$，表示树上每个节点写的数值。

接下来 $n-1$ 行，每行两个正整数 $x,y$，表示一条边连接节点 $x$ 和 $y$（$1\le x,y\le n$，$x\ne y$）。保证图是一棵树。

输出格式：

输出一个数，表示 ${\sum }_{i=1}^n{\sum }_{j=i}^{n}I(i,j)$。

题目描述

You are given a tree $ T $ consisting of $ n $ vertices. A number is written on each vertex; the number written on vertex $ i $ is $ a_{i} $ . Let’s denote the function $ I(x,y) $ as the difference between maximum and minimum value of $ a_{i} $ on a simple path connecting vertices $ x $ and $ y $ .

Your task is to calculate ${\sum }_{i=1}^n{\sum }_{j=1}^{n}I(i,j)$.

输入格式

The first line contains one integer number $ n $ ( $ 1<=n<=10^{6} $ ) — the number of vertices in the tree.

The second line contains $ n $ integer numbers $ a_{1} $ , $ a_{2} $ , …, $ a_{n} $ ( $ 1<=a_{i}<=10^{6} $ ) — the numbers written on the vertices.

Then $ n-1 $ lines follow. Each line contains two integers $ x $ and $ y $ denoting an edge connecting vertex $ x $ and vertex $ y $ ( $ 1<=x,y<=n $ , $ x≠y $ ). It is guaranteed that these edges denote a tree.

输出格式

Print one number equal to ${\sum }_{i=1}^n{\sum }_{j=1}^{n}I(i,j)$

样例 #1

样例输入 #1

4
2 2 3 1
1 2
1 3
1 4

样例输出 #1

6

题解

分析

把这道题转化一下, 变成了求任意两点之间经过点权最大值之和减去最小值之和,即

$$\sum _{i=1}^n\sum _{j=1}^{n}max(i\to j)-\sum _{i=1}^n\sum _{j=1}^{n}min(i\to j)$$

这两部分原理近似,考虑前一部分

现在我们将这些边按照权值排序(边权为两个点权较大的一方),由小到大,这样能保证加边时边权是当前图中最大的. 那么边所连接的两点为根的子树中所有点到达另一颗子树中的所有点,所经过的最大值一定是新加入的这条边

使用连通块维护连通性和子树大小即可

AC Code

#include <bits/stdc++.h>
using namespace std;
#define N 1000010
namespace Radon{void Main();
}
int main(){Radon::Main();return 0;
}namespace Radon{#define int long longint n;int a[N],fa[N],siz[N];int ans=0;struct edge{int u,v;int maxn,minx;}e[N];bool cmp_max(edge A,edge B){return A.maxn<B.maxn;}bool cmp_min(edge A,edge B){return A.minx>B.minx;}int find(int x){if(fa[x]==x){return x;}fa[x]=find(fa[x]);return fa[x];}void init_max(){sort(e+1,e+1+(n-1),cmp_max);for(int x=1;x<=n;x++){fa[x]=x;siz[x]=1;}}void init_min(){sort(e+1,e+1+(n-1),cmp_min);for(int x=1;x<=n;x++){fa[x]=x;siz[x]=1;}}void Main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// freopen("CF915F.in","r",stdin);// freopen("CF915F-me.out","w",stdout);cin >> n;for(int x=1;x<=n;x++){cin >> a[x];}for(int x=1;x<n;x++){cin >> e[x].u >> e[x].v;int u=e[x].u;int v=e[x].v;e[x].maxn=max(a[u],a[v]);e[x].minx=min(a[u],a[v]);}init_max();for(int x=1;x<n;x++){int u=e[x].u,v=e[x].v;int maxn=e[x].maxn;int fu=find(u);int fv=find(v);// cout << u << ' ' << v << ':';// cout << maxn << ' ' << fu << ' ' << fv << " ^^ ";// cout << siz[fu] << ' ' << siz[fv] << '&' << fa[fu] << ' ' << fa[fv];// cout << "-->" << fa[fu] << ' ' << fa[fv] << endl;ans+=siz[fu]*siz[fv]*maxn;fa[fu]=fv;siz[fv]+=siz[fu];}// cout << ans << endl;init_min();for(int x=1;x<n;x++){int u=e[x].u,v=e[x].v;int minx=e[x].minx;int fu=find(u);int fv=find(v);// cout << u << ' ' << v << ':';// cout << minx << ' ' << fu << ' ' << fv << " ^^ ";// cout << siz[fu] << ' ' << siz[fv] << '&' << fa[fu] << ' ' << fa[fv];// cout << "-->" << fa[fu] << ' ' << fa[fv] << endl;ans-=siz[fu]*siz[fv]*minx;fa[fu]=fv;siz[fv]+=siz[fu];}cout << ans;}
}