酒店网站 方案,琪歌 wordpress,临沂网站建设培训班,全网营销外包传送门 数学还是太差了#xff0c;想了半天都没想出来 首先有一个定理#xff0c;如果直径#xff08;这里考虑经过的点数#xff09;为奇数#xff0c;所有直径有同一个中点#xff0c;如果直径为偶数#xff0c;所有直径有同一条最中间的边。这个可以用反证法#xf…传送门 数学还是太差了想了半天都没想出来 首先有一个定理如果直径这里考虑经过的点数为奇数所有直径有同一个中点如果直径为偶数所有直径有同一条最中间的边。这个可以用反证法假设不成立的话直径会变长 如果直径为奇数那么我们可以以共同经过的那个点为根把所有在直径上的叶子按不同的子树分类如果某两个叶子在同一棵子树那么它们不可能构成直径如果在不同的子树那么必定能构成直径。所以把所有在直径上的叶子按不同的子树分为若干个集合 如果是偶数那么就直接分为两个集合 我们现在要求的就是这些集合中只剩一个集合没有被完全染黑的期望时间 可以考虑容斥枚举一个集合\(i\)让它成为没有被完全染黑的那个集合那么我们现在只关心其它所有集合被全部染黑的时间设\(m\)为叶子总数\(s\)为剩下的集合中点的总数设\(f_i\)为还剩下\(i\)个点没有被染色时染一个点的期望时间那么有\(f_i1\frac{m-i}{m}f_i\)所以\(f_i\frac{m}{i}\)那么剩下的集合全部被染色的时间就是\(\sum_{i1}^{s}\frac{m}{i}\)预处理一下就可以了 然而按我们上面的枚举方法有可能会有所有集合都被染黑的情况。考虑每一种所有集合都被染黑的方案如果最后一个被染黑的集合黑了那么其他集合肯定也黑了。所以每一个方案中每一个最后被染黑的集合会被其它所有集合枚举到\(t-1\)次\(t\)为集合的个数也就是说每一种全被染黑的方案会被统计\(t-1\)次减掉就好了 //minamoto
#includebits/stdc.h
#define R register
#define fp(i,a,b) for(R int ia,Ib1;iI;i)
#define fd(i,a,b) for(R int ia,Ib-1;iI;--i)
#define go(u) for(int ihead[u],ve[i].v;i;ie[i].nx,ve[i].v)
using namespace std;
char buf[121],*p1buf,*p2buf;
inline char getc(){return p1p2(p2(p1buf)fread(buf,1,121,stdin),p1p2)?EOF:*p1;}
int read(){R int res,f1;R char ch;while((chgetc())9||ch0)(ch-)(f-1);for(resch-0;(chgetc())0ch9;resres*10ch-0);return res*f;
}
char sr[121],z[20];int C-1,Z0;
inline void Ot(){fwrite(sr,1,C1,stdout),C-1;}
void print(R int x){if(C120)Ot();if(x0)sr[C]-,x-x;while(z[Z]x%1048,x/10);while(sr[C]z[Z],--Z);sr[C]\n;
}
const int N5e55,P998244353;
inline int add(R int x,R int y){return xyP?xy-P:xy;}
inline int dec(R int x,R int y){return x-y0?x-yP:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){R int res1;for(;y;y1,xmul(x,x))if(y1)resmul(res,x);return res;
}
struct eg{int v,nx;}e[N1];int head[N],tot;
inline void add_edge(R int u,R int v){e[tot]{v,head[u]},head[u]tot;}
int inv[N],sum[N],dep[N],fa[N],deg[N],st[N];
int n,tmp,res,u,v,len,m,top,s,ans;
void dfs(int u,int fat,int x){fa[u]fat,dep[u]dep[fat]1;if(dep[u]len/2)x;go(u)if(v!fat)dfs(v,u,x);
}
int main(){
// freopen(testdata.in,r,stdin);nread();fp(i,1,n-1){uread(),vread(),add_edge(u,v),add_edge(v,u);deg[u],deg[v];}int rt1,tl1;dfs(1,0,tmp);fp(i,1,n){if(dep[i]dep[rt])rti;if(deg[i]1)m;}dfs(rt,0,tmp);fp(i,1,n)if(dep[i]dep[tl])tli;lendep[tl];inv[1]1,sum[1]m;fp(i,2,n){inv[i]1ll*inv[P%i]*(P-P/i)%P;sum[i]add(sum[i-1],mul(m,inv[i]));}if(len1){int x0;for(R int itl;i;ifa[i])if(dep[i]((len1)1))xi;dep[x]0;go(x){dfs(v,x,tmp0);if(tmp)st[top]tmp,stmp;}}else{int x10,x20;for(R int itl;i;ifa[i]){if(dep[i](len1))x1i;if(dep[i](len1)1)x2i;}dep[x2]0,dfs(x1,x2,st[top]);dep[x1]0,dfs(x2,x1,st[top]);sst[1]st[2];}fp(i,1,top)ansadd(ans,sum[s-st[i]]);printf(%d\n,dec(ans,mul(top-1,sum[s])));return 0;
} 转载于:https://www.cnblogs.com/bztMinamoto/p/10248265.html
