これはすんなり。
http://codeforces.com/contest/915/problem/F
問題
木を成す無向グラフが与えられる。
各頂点には数値が設定されている。
2頂点u,vに対し
I(u,v) := パスu-v間にある頂点上の数値の最大値と最小値の差
とする。全頂点ペアにおけるI(u,v)の総和を求めよ。
解法
A(u,v) := パスu-v間にある頂点上の数値の最大値
B(u,v) : = 同最小値の差
とするとI(u,v) = A(u.v)-B(u,v)となる。
そこでAの総和とBの総和を個別に求めよう。
以下Aの総和について考える。
全ての頂点が無効の状態から、頂点を数値の小さい順に徐々に有効化していくことを考える。
辺の両端の頂点が有効になると、辺も有効になる。
さて、ある点vが有効化され、それに伴いいくつかの辺が有効となることで、いくつかの連結成分全体がvを開始1つの連結成分になったとする。
この時、この連結成分のうち異なる2つの連結成分から1頂点ずつs,tを選ぶと、そのパスは必ずvを通る。
頂点は数値の小さい順に有効化しているので、vを通るパスは必ずA(s,t)=vとなる。
よって、連結成分とその成分数をUnion-Findで管理していけばA(s,t)の総和が求められる。
int N; int A[1010101]; vector<int> E[1010101]; pair<int,int> P[1010101]; int S[1010101]; template<int um> class UF { public: vector<int> par,rank,cnt; UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;} void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;} int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));} int count(int x) { return cnt[operator[](x)];} int operator()(int x,int y) { if((x=operator[](x))==(y=operator[](y))) return x; cnt[y]=cnt[x]=cnt[x]+cnt[y]; if(rank[x]>rank[y]) return par[x]=y; rank[x]+=rank[x]==rank[y]; return par[y]=x; } }; UF<1010101> uf[2]; void solve() { int i,j,k,l,r,x,y; string s; scanf("%d",&N); FOR(i,N) { scanf("%d",&A[i]); P[i]={A[i],i}; } FOR(i,N-1) { scanf("%d%d",&x,&y); E[x-1].push_back(y-1); E[y-1].push_back(x-1); } sort(P,P+N); ll ret=0; FOR(i,N) { x=P[i].second; S[x]=1; int cur=1; FORR(e,E[x]) if(S[e]==1) { ret += 1LL*A[x]*uf[0].count(x)*uf[0].count(e); uf[0](x,e); } } FOR(i,N) { x=P[N-1-i].second; S[x]=2; int cur=1; FORR(e,E[x]) if(S[e]==2) { int nv=uf[1].count(e); ret -= 1LL*A[x]*uf[1].count(x)*uf[1].count(e); uf[1](x,e); } } cout<<ret<<endl; }
まとめ
これはありがちな問題かも。