これは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も回ごとにちょっと難易度のブレがあるかもね。