AtCoder Beginner Contest 149
問題文
省略
省略
C++に変換後のコードはこちら
int N, A[2d5], B[2d5];
Modint res;
graph g;
int sz[2d5];
int arr[2d5], s;
Modint pw[2d5+1], ipw[2d5+1];
void doit(int n){
Modint tmp;
sz[n] = 1;
rep[g.edge[n]](i,g.es[n]){
doit(i);
sz[n] += sz[i];
}
s = 0;
if(sz[n]!=N) arr[s++] = N - sz[n];
rep[g.edge[n]](i,g.es[n]) arr[s++] = sz[i];
if(s >= 2){
tmp = 1;
tmp -= ipw[N-1];
rep(i,s) tmp -= (1 - ipw[arr[i]]) * ipw[N-1-arr[i]];
res += tmp / 2;
}
}
{
pw[0] = 1;
rep(i,2d5) pw[i+1] = 2 * pw[i];
rep(i,2d5+1) ipw[i] = 1 / pw[i];
rd(N,(A--,B--)(N-1));
g.setEdgeRootedTree(N,N-1,A,B);
doit(0);
wt(res);
}
Current time: 2024年03月29日22時41分28秒
Last modified: 2020年01月19日05時12分00秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC149 ABC_F
トップページに戻る
Logged in as: unknown user (not login)