AtCoder ABC #419 : G - Count Simple Paths 2

Fまでは順調だったのだが。
https://atcoder.jp/contests/abc419/tasks/abc419_g

問題

N点M辺の連結無向グラフが与えられる。
頂点1から頂点Nに至る単純パスが何個あるか、長さごとに個数を答えよ。

解法

K=(M-(N-1))とすると、単純パスの個数は高々2^K個である。
とはいえDFSで、(頂点番号,ここまでの長さ)を状態として総当たりするとO(N*2^K)かかりTLEする。

そこで頂点を縮約する。
絶対に到達しない頂点、すなわち頂点1,N以外で次数1の点は削除する。
次に、次数2の点も縮約し、辺に長さを持たせるようにする。
そうすると頂点数がO(K)程度になるので、DFSもO(K*2^K)で済むようになる。

int N,M;
set<pair<int,int>> E[202020];
int ret[202020];
int vis[202020];

void dfs(int cur,int d) {
	if(cur==N-1) {
		ret[d]++;
		return;
	}
	vis[cur]=1;
	FORR2(e,c,E[cur]) if(vis[e]==0) dfs(e,c+d);
	vis[cur]=0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].insert({y-1,1});
		E[y-1].insert({x-1,1});
	}
	queue<int> Q;
	FOR(i,N) if(i!=0&&i!=N-1&&E[i].size()==1) Q.push(i);
	while(Q.size()) {
		int cur=Q.front();
		Q.pop();
		int e=E[cur].begin()->first;
		E[cur].clear();
		E[e].erase({cur,1});
		if(E[e].size()==1) Q.push(e);
	}
	
	FOR(i,N) if(i!=0&&i!=N-1&&E[i].size()==2) {
		auto p1=*E[i].begin();
		auto p2=*next(E[i].begin());
		E[p1.first].erase({i,p1.second});
		E[p2.first].erase({i,p2.second});
		E[p1.first].insert({p2.first,p1.second+p2.second});
		E[p2.first].insert({p1.first,p1.second+p2.second});
	}
	
	dfs(0,0);
	
	for(i=1;i<=N-1;i++) cout<<ret[i]<<" ";
	cout<<endl;
}

まとめ

全体でO(K*2^K)程度にできるんだろうなと思いつつ、具体的な手順が思いつかず…。