kmjp's blog

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

第13回 アルゴリズム実技検定 : M - 木と区間

これはPASTのM問題にしても簡単?
https://atcoder.jp/contests/past202212-open/tasks/past202212_m

問題

1~NのN頂点からなる無向グラフが与えられる。
整数区間[L,R]に対し、以下の総和を求めよ。

  • 1番の頂点以外に、[L,R]の範囲の点だけ通って到達できる点の数

解法

1番から各点に至るまでに、通過した頂点番号の最小値と最大値を求めよう。
そうすれば、その点に至ることができるL,Rの範囲がわかる。

int N;
vector<pair<int,int>> E[202020];
ll ret;

void dfs(int cur,int pre,int mi,int ma) {
	if(cur==0) {
		ret+=1LL*N*(N-1)/2;
	}
	else {
		ret+=1LL*(mi+1)*(N-1-ma);
	}
	FORR2(e,c,E[cur]) if(e!=pre) dfs(e,cur,min(mi,c),max(ma,c));
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back({y-1,i});
		E[y-1].push_back({x-1,i});
	}
	dfs(0,0,N-1,0);
	cout<<ret<<endl;
}

まとめ

こうしてみるとPASTも回ごとにちょっと難易度のブレがあるかもね。