[noi simulation] Anaid's tree (Mobius inversion, exponential generating function, Ehrlich sieve, virtual tree)

Topic

512mb, 4s

$1\le n\le 10^5,0\le K\le 10,1\le u,v\le n$ .

Answer key

We first have this formula ：
$$\varphi (xy)=\varphi (x)\varphi (y)\cdot \frac{gcd(x,y)}{\varphi (gcd(x,y))}$$

Then you can substitute the answer
$$\begin{gathered} \sum _{i=1}^n\sum _{j=1}^n\varphi (ij)d^k(i,j)=\sum _{i=1}^n\sum _{j=1}^n\varphi (i)\varphi (j)\frac{gcd(i,j)}{\varphi (gcd(i,j))}{d}^k(i,j) \\ =\sum _{g=1}^n\frac{g}{\varphi (g)}\sum _{i=1}^n\sum _{j=1}^n\varphi (i)\varphi (j)[gcd(i,j)=g]d^k(i,j) \end{gathered}$$

In this step, let's use a simple method ：
$$\begin{gathered} =\sum _{g=1}^n\frac{g}{\varphi (g)}\sum _{g|T}\mu (T/g)\sum _{T|i}^n\sum _{T|j}^n\varphi (i)\varphi (j)d^k(i,j) \\ =\sum _{T=1}^n\left(\sum _{T|i}^n\sum _{T|j}^n\varphi (i)\varphi (j)d^k(i,j)\right)\left(\sum _{g|T}\frac{g}{\varphi (g)}\mu (T/g)\right) \end{gathered}$$

Then we can preprocess the lump on the right .

Violence enumeration $T$ There are a total of $O(n\ln n)$ individual . We're interested in every $T$ , Take out all $T$ Multiple , Build a virtual tree .

Two points $A,B$ stay $lca$ Make a contribution to , Suppose the length of the left part is $a$ , The length of the right part is $b$ , How to merge the two ？

We consider that $k=0\sim K$ Put the situation of $EGF$ in , Concrete ,
$$F_A=\sum _{i=0}^K\varphi (A)a^i\cdot \frac{x^i}{i!},F_B=\sum _{i=0}^K\varphi (B)b^i\cdot \frac{x^i}{i!}$$

hold $F_A,F_B$ Multiply , Convolution can get $k=0\sim K$ Of $\varphi (i)\varphi (j)d^k(i,j)$ .

therefore , Let's do the virtual tree $\mathrm{d}\mathrm{f}\mathrm{s}$ , Process each subtree to reach each descendant $EGF$ And , Merging the contributions of two subtrees will directly $EGF$ Just multiply it .

take $A$ Of $EGF$ from $a^k$ Extended to $(a+1{)}^k$ You can roll one $\sum \frac{x^i}{i!}$ .

Time complexity $O(n\ln n(\log n+K^2))$ .

CODE

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<random>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#pragma GCC optimize(2)
using namespace std;
#define MAXN 100005
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define PR pair<int,int>
#define UIN unsigned int
int xchar() {
    
	static const int maxn = 1000000;
	static char b[maxn];
	static int pos = 0,len = 0;
	if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
#define getchar() xchar()
inline LL read() {
    
	LL f = 1,x = 0;int s = getchar();
	while(s < '0' || s > '9') {
    if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
	while(s >= '0' && s <= '9') {
    x = (x<<1) + (x<<3) + (s^48);s = getchar();}
	return f*x;
}
void putpos(LL x) {
    if(!x)return ;putpos(x/10);putchar((x%10)^48);}
inline void putnum(LL x) {
    
	if(!x) {
    putchar('0');return ;}
	if(x<0) putchar('-'),x = -x;
	return putpos(x);
}
inline void AIput(LL x,int c) {
    putnum(x);putchar(c);}

const int MOD = 998244353;
int n,m,s,o,k;
inline void MD(int &x) {
    if(x>=MOD)x-=MOD;}
int inv[MAXN],fac[MAXN],invf[MAXN];
vector<int> fc[MAXN];
int p[MAXN],cnt,f[MAXN],mu[MAXN],F[MAXN],dv[MAXN],phi[MAXN];
void init(int n) {
    
	inv[0] = inv[1] = 1;
	for(int i = 2;i <= max(n,15);i ++) inv[i] = (MOD-inv[MOD%i]) *1ll* (MOD/i) % MOD;
	fac[0] = invf[0] = 1;
	for(int i = 1;i <= 15;i ++) {
    
		fac[i] = fac[i-1] *1ll* i % MOD;
		invf[i] = invf[i-1] *1ll* inv[i] % MOD;
	}
	f[1] = 1; cnt = 0; mu[1] = 1; dv[1] = 1; phi[1] = 1;
	for(int i = 2;i <= n;i ++) {
    
		if(!f[i]) {
    
			p[++ cnt] = i;
			mu[i] = -1;phi[i] = i-1;dv[i] = i*1ll*inv[i-1]%MOD;
		}
		for(int j = 1,nm;j <= cnt && (nm=i*p[j]) <= n;j ++) {
    
			f[nm] = 1;
			if(i % p[j] == 0) {
    
				mu[nm] = 0; phi[nm] = phi[i]*p[j];
				dv[nm] = dv[i]; break;
			}
			mu[nm] = -mu[i]; phi[nm] = phi[i]*phi[p[j]];
			dv[nm] = dv[i] *1ll* dv[p[j]] % MOD;
		}
	}
	for(int i = 1;i <= n;i ++) {
    
		for(int j = i,k = 1;j <= n;j += i,k ++) {
    
			fc[j].push_back(i);
			MD(F[j] += (MOD+mu[i])*1ll*dv[k]%MOD);
		}
	} return ;
}
int a[MAXN],dfn[MAXN],tim;
inline bool cmp(int a,int b) {
    return dfn[a] < dfn[b];}
vector<int> g[MAXN];
int d[MAXN],fa[MAXN][20];//17
void dfs0(int x,int ff) {
    
	d[x] = d[fa[x][0] = ff] + 1; dfn[x] = ++ tim;
	for(int i = 1;i <= 17;i ++) fa[x][i] = fa[fa[x][i-1]][i-1];
	for(int y:g[x]) if(y != ff) dfs0(y,x);
	return ;
}
int lca(int a,int b) {
    
	if(d[a] < d[b]) swap(a,b);
	if(d[a] > d[b]) for(int i = 17;i >= 0;i --) {
    
		if(d[fa[a][i]] >= d[b]) a = fa[a][i];
	} if(a == b) return a;
	for(int i = 17;i >= 0;i --) {
    
		if(fa[a][i] ^ fa[b][i]) {
    
			a = fa[a][i]; b = fa[b][i];
		}
	} return fa[a][0];
}
int tg[MAXN],wt[MAXN];
int hd[MAXN],nx[MAXN<<1],v[MAXN<<1],w[MAXN<<1],cne;
void ins(int x,int y,int z) {
    
	nx[++cne] = hd[x]; v[cne] = y; hd[x] = cne; w[cne] = z;
}
struct vec{
    
	int s[11];
	vec(){
    memset(s,0,sizeof(s));}
	vec(int d) {
    
		for(int i = 0,p = 1;i <= m;i ++,p = p*1ll*d%MOD)
			s[i] = p*1ll*invf[i] % MOD;
	}
}dp[MAXN];
inline vec operator * (vec a,vec b) {
    
	for(int i = m;i >= 0;i --) {
    
		int nm = 0;
		for(int j = 0;j <= i;j ++) {
    
			nm = (nm + a.s[i-j]*1ll*b.s[j]) % MOD;
		} a.s[i] = nm;
	} return a;
}
inline vec& operator *= (vec &a,vec b) {
    
	for(int i = m;i >= 0;i --) {
    
		int nm = 0;
		for(int j = 0;j <= i;j ++) {
    
			nm = (nm + a.s[i-j]*1ll*b.s[j]) % MOD;
		} a.s[i] = nm;
	} return a;
}
inline vec& operator += (vec &a,vec b) {
    
	for(int i = 0;i <= m;i ++) {
    
		MD(a.s[i] += b.s[i]);
	} return a;
}
vec as;
void dfs(int x,int ff) {
    
	dp[x] = vec(); MD(dp[x].s[0] += wt[x]);
	MD(as.s[0] += wt[x]*1ll*wt[x]%MOD*inv[2]%MOD);
	for(int i = hd[x];i;i = nx[i]) {
    
		int y = v[i]; if(y == ff) continue;
		dfs(y,x); dp[y] *= vec(w[i]);
		as += dp[x] * dp[y];
		for(int j = 0;j <= m;j ++) MD(dp[x].s[j] += dp[y].s[j]);
	}
	return ;
}
int st[MAXN],tp;
int main() {
    
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	n = read(); m = read();
	init(n);
	for(int i = 1;i < n;i ++) {
    
		s = read();o = read();
		g[s].push_back(o);
		g[o].push_back(s);
	}
	dfs0(1,0);
	vec ans;
	for(int D = 1;D <= n;D ++) {
    
		int cn = 0; cne = 0;
		for(int j = D;j <= n;j += D) {
    
			a[++ cn] = j; wt[j] = phi[j];
			tg[j] = D; hd[j] = 0;
		}
		sort(a + 1,a + 1 + cn,cmp);
		st[tp = 1] = a[1];
		for(int i = 1;i <= cn;i ++) {
    
			int x = a[i],lc = lca(x,st[tp]),p = 0;
			if(tg[lc] != D) {
    
				tg[lc] = D; wt[lc] = hd[lc] = 0;
			}
			while(tp > 0 && d[st[tp]] > d[lc]) {
    
				if(p) ins(st[tp],p,d[p]-d[st[tp]]);
				p = st[tp --];
			}
			if(p) ins(lc,p,d[p] - d[lc]);
			if(st[tp] != lc) st[++ tp] = lc;
			if(x != lc) st[++ tp] = x;
		}
		int p = 0;
		while(tp > 0) {
    
			if(p) ins(st[tp],p,d[p]-d[st[tp]]);
			p = st[tp --];
		}
		as = vec();
		dfs(p,0);
		for(int i = 0;i <= m;i ++) as.s[i] = as.s[i] *2ll* F[D] % MOD;
		ans += as;
	}
	for(int i = 0;i <= m;i ++) {
    
		AIput(ans.s[i]*1ll*fac[i]%MOD,'\n');
	}
	return 0;
}