AtCoder ABC #173 : F - Intervals on Tree

コードも短いしね。
https://atcoder.jp/contests/abc173/tasks/abc173_f

問題

1～Nの番号を持つ頂点からなる木を成す無向グラフが与えられる。
f(L,R)を、L～Rの番号の頂点とその誘導部分グラフにおける連結成分数とする。
1≦L≦R≦Nにおけるf(L,R)の総和を求めよ。

解法

まずL,Rを総当たりしたときの頂点数の総和を求めよう。
もし1つの辺が有効となる場合、連結成分が1つ減る。
そこで、辺(u,v)に対し、(u,v)に辺が張られるL,Rの組み合わせの分上記総和から引けばよい。

int N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll ret=0;
	FOR(i,N) ret+=1LL*(i+1)*(N-i);
	FOR(i,N-1) {
		cin>>x>>y;
		x--;
		y--;
		if(x>y) swap(x,y);
		ret-=1LL*(x+1)*(N-y);
	}
	cout<<ret<<endl;
}

まとめ

これEとFの問題順が逆だったら正答数どうなってたかな。