AtCoder Beginner Contest 149 F問題 - Surrounded Nodes

Source

AtCoder Beginner Contest 149
問題文

問題概要

省略

解法

省略

cLayversion 20200119-1)のコード

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: 2021年09月18日03時36分24秒
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)

ログイン: