CF1554E You

在到校两个小时二十分钟后，我终于开始决定写题。

我们考虑实际上这个 \(a_i\) 数组，必然与我们直接定向每一条边之后每个点的出度数组一一对应。

然后就去吃饭了好耶！

在到校四个小时四十分钟后，我终于开始继续写题。

我们再来考虑如何求出这个 \(\gcd(a_1,a_2,\cdots,a_n)=k\) 。

感觉可以考虑莫反，我们令 \(g(i)\) 表示恰好 \(\gcd\) 为 \(i\) 的方案数，\(f(i)\) 表示 \(\gcd\) 为 \(i\) 的倍数的方案数。

我们考虑 \(f(d)\) 怎么算。我们发现，实际上我们只需要满足每一棵子树中的 \(siz_u\) 加上该子树连向父亲的边的对该子树根的出度贡献是 \(d\) 的倍数，就是一种方案。

我们就直接考虑算出所有的可能的 \(d\) 的 \(f(d)\) ，然后用调和级数来计算 \(g(k)\) 就行了。

我们再来考虑可能的 \(d\) 的范围，实际上就是 \(n-1\) 的因数。我们考虑暴力枚举因数然后判断就行了吧。

#include
using namespace std;
const int N=1e5+5;
const int MOD=998244353;
int ADD(int x,int y){return x+y>=MOD?x+y-MOD:x+y;}
int TIME(int x,int y){return (int)(1ll*x*y%MOD);}
int n,siz[N],f[N],g[N];
struct Edge{int nxt,to;}e[N<<1];int fir[N];
void add(int u,int v,int i){e[i]=(Edge){fir[u],v},fir[u]=i;}
void dfs(int u,int fa){
	siz[u]=1;
	for(int i=fir[u];i;i=e[i].nxt){
		int v=e[i].to;if(v==fa) continue;
		dfs(v,u),siz[u]+=siz[v];
	}
}
int check(int k){
	int res=1;
	for(int i=2;i<=n;++i)
	res=TIME(res,(siz[i]%k==0)+((siz[i]-1)%k==0));
	return res;
}
int mu[N];bool tag[N];
vector pri;
void init(){
	mu[1]=1;
	for(int i=2;i=N) break;
			tag[i*pri[j]]=true;
			if(i%pri[j]==0){mu[i*pri[j]]=0;break;}
			else mu[i*pri[j]]=TIME(mu[i],mu[pri[j]]);
		}
	}
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;++i) fir[i]=0;
	for(int i=1;i>T;
	while(T--) solve();
	return 0;
}