Codeforces #735 Div2 : E. You

これはDiv2にしては全完が多かった回。
https://codeforces.com/contest/1554/problem/E

問題

木を成すN頂点の無向グラフが与えられる。
ここから、N点を1つずつ(辺と合わせて)取り除き、その際取り除く直前の次数を列挙することを考える。
この次数のGCDがKとなるケースは、取り除き方N!通り中何通りか、K=1～Nそれぞれに対し求めよ。

解法

次数を列挙するとその和は(N-1)なので、Kが(N-1)の約数であるケースだけを考える。
f(k) := GCDがkの倍数となる取り除き方の数
g(k) := GCDがkとなる取り除き方の数
とすると、g(k) = f(k) -g(2k) - g(3k) - ...となる。

k=1の時は自明なので、kが2以上のケースを考える。
DFSでSubTree内を条件を満たしながら消せるか判定しよう。
その際、子頂点を条件を満たすように(消すときに次数がkの倍数となるように)消せるか考えていくと、親頂点と自身のどちらを先に消すべきか(もしくはどちらを先に消しても、自身を次数がkの倍数の状態で消すことができない)が自明に定まる。

int T;
int N;
vector<int> E[101010];

const ll mo=998244353;
ll pat[101010];
int C[101010];


int dfs(int cur,int pre,int v) {
	
	FORR(e,E[cur]) if(e!=pre) {
		if(dfs(e,cur,v)==0) return 0;
	}
	
	if(C[cur]%v==0) {
		C[pre]++;
	}
	else if((C[cur]+1)%v) {
		return 0;
	}
	else {
		if(cur==0) return 0;
	}
	return 1;
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			E[i].clear();
			pat[i+1]=0;
		}
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		for(i=N;i>=1;i--) {
			if((N-1)%i) continue;
			
			if(i==1) {
				pat[i]=1;
				FOR(j,N-1) pat[i]=pat[i]*2%mo;
			}
			else {
				FOR(j,N) C[j]=0;
				pat[i]=dfs(0,0,i);
			}
			
			for(j=i*2;j<=N;j+=i) (pat[i]+=mo-pat[j])%=mo;;
		}
		
		for(i=1;i<=N;i++) cout<<pat[i]<<" ";
		cout<<endl;
		
	}
}

まとめ

この回問題名がよくわからないな。