kmjp's blog

競技プログラミング参加記です

Codeforces ECR #036: F. Imbalance Value of a Tree

これはすんなり。
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;
}

まとめ

これはありがちな問題かも。