こういう考察苦手だな…。
https://atcoder.jp/contests/arc125/tasks/arc125_f
問題
N頂点の木を成すグラフが与えられる。
この時、任意の頂点x個を選んだ時に、その点の次数の総和をyとしたとき、(x,y)として取れる値は何通りか。
解法
各点vの次数から1引いた値をd[v]とする。
vをx個選んだ時、sum(d[v])=yとなるyの数を数え上げたい。
証明はEditorialを参照頂くとして、yを固定すると実は対応するxは連続する単一の区間となる。
そこで、y、すなわちd[v]の総和に対し、対応するxの最小値と最大値をDPで処理して行こう。
d[v]が一致する値を一括して扱うと、この問題はO(N√N)で解ける。
int N; int C[202020]; int ma[202020]; int mi[202020]; deque<pair<int,int>> Dmi[202020],Dma[202020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N-1) { cin>>x>>y; C[x-1]++; C[y-1]++; } map<int,int> M; FOR(i,N) M[C[i]-1]++; FOR(i,N+2) mi[i]=1<<30, ma[i]=-1<<30; mi[0]=0; ma[0]=M[0]; int sum=0; FORR2(a,b,M) if(a) { sum+=a*b; FOR(i,sum+1) { x=i%a; int pmi=mi[i]; int pma=ma[i]; if(Dmi[x].size()&&(i-Dmi[x].front().first)/a>b) Dmi[x].pop_front(); if(Dma[x].size()&&(i-Dma[x].front().first)/a>b) Dma[x].pop_front(); if(Dmi[x].size()) mi[i]=min(mi[i],Dmi[x].front().second+(i-Dmi[x].front().first)/a); if(Dma[x].size()) ma[i]=max(ma[i],Dma[x].front().second+(i-Dma[x].front().first)/a); while(Dmi[x].size()&&Dmi[x].back().second+(i-Dmi[x].back().first)/a>=pmi) Dmi[x].pop_back(); while(Dma[x].size()&&Dma[x].back().second+(i-Dma[x].back().first)/a<=pma) Dma[x].pop_back(); Dmi[x].push_back({i,pmi}); Dma[x].push_back({i,pma}); } FOR(i,a) Dmi[i].clear(),Dma[i].clear(); } ll ret=0; FOR(i,N) if(ma[i]>=mi[i]) { ret+=ma[i]-mi[i]+1; } cout<<ret<<endl; }
まとめ
xに対して、yは不連続な値を取れるな…と思って手が止まってしまった。
色々実験すれば気づけたのかな。