上海网站备案管理中心,厦门建设网站首页,wordpress本地网站搭建整套课程,做公益网站有什么要求E. You
首先我们假设每个节点有个点权#xff0c;点权是儿子的数量。
一个点可以和他的父亲所要权值1#xff08;先删去自己#xff0c;再删去父亲#xff09;#xff0c;并且此操作不可逆。于是dfs从叶子节点一次递推即可得出某个kkk是否能作为gcd\gcdgcd。
由于上述…E. You
首先我们假设每个节点有个点权点权是儿子的数量。
一个点可以和他的父亲所要权值1先删去自己再删去父亲并且此操作不可逆。于是dfs从叶子节点一次递推即可得出某个kkk是否能作为gcd\gcdgcd。
由于上述“权值交换”的过程只会变化1并且权值和一定是n-1只需要枚举n-1的约数一一dfs递推判断即可。
注意最后需要容斥一下重复计算的情况 upd我们在dfs时并没有直接考虑gcd\gcdgcd而是通过考虑点权是否是gcd\gcdgcd的倍数显然如果一个是6的倍数自然也是2的倍数但gcd要求我们是最大公约数所以由于2的答案是依附于6的基础上需要减去。
#includebits/stdc.h
using namespace std;
using lllong long;
template class Tint T rd()
{T res0;T fg1;char chgetchar();while(!isdigit(ch)) {if(ch-) fg-1;chgetchar();}while( isdigit(ch)) res(res1)(res3)(ch^48),chgetchar();return res*fg;
}
const int N100010,mod998244353;vectorint g[N];
int a[N],n;
ll ans[N];
bool dfs(int u,int fa,int val)
{for(auto v:g[u]){if(vfa) continue;if(!dfs(v,u,val)) return 0;}if(a[u]%val0){if(fa) a[fa];return 1;}if((a[u]1)%val0fa) return 1;return 0;
}
void init()
{for(int i1;in;i) ans[i]0;for(int i1;in;i) a[i]0;for(int i1;in;i) g[i].clear();
}
int main()
{int Tcrd();while(Tc--){init();nrd();for(int i1;in;i){int urd(),vrd();g[u].push_back(v);g[v].push_back(u);}for(int i1;in;i)if((n-1)%i0){if(i1) {ans[1]1;for(int i1;in;i) ans[1]ans[1]*2%mod;continue;}for(int i1;in;i) a[i]0;if(dfs(1,0,i)) ans[i];}for(int in;i1;i--)for(int j2;i*jn;j)ans[i](ans[i]-ans[i*j]mod)%mod;for(int i1;in;i) printf(%lld%c,ans[i], \n[in]);}return 0;
}
