AtCoder Beginner Contest 163 F問題 - path pass i

Source

AtCoder Beginner Contest 163
問題文

問題概要

省略

解法

省略

cLay（version 20200430-1）のコード

C++に変換後のコードはこちら

int N, A[2d5], B[2d5], C[2d5];
graph g;
HLD hld;

int pre[2d5], sz[2d5];
vector<int> b[2d5];

ll res[2d5];

int solve(int r, int &ind, vector<int> &b, ll &res){
  int i, k = 0, nx, s = 0, em;

  if(r==-1){
    while(ind < b.size()){
      i = ind++;
      s += solve(b[i], ind, b, res);
    }
    em = N - s;
    res -= (ll)em * (em+1) / 2;
  } else {
    rep(k,g.es[r]) if(g.edge[r][k] != hld.up(r)){
      nx = g.edge[r][k];
      while(ind < b.size() && hld.lca(nx, b[ind]) == nx){
        i = ind++;
        s += solve(b[i], ind, b, res);
      }
      em = sz[nx] - s;
      res -= (ll)em * (em+1) / 2;
      s = 0;
    }
  }
  return if[r==-1, -1, sz[r]];
}

{
  int ind;
  rd(N,(C--)(N),(A--,B--)(N-1));
  g.setEdge(N,N-1,A,B);
  hld.init(g);

  g.preorder(pre);
  g.SubTreeSize(0, sz);

  rep(i,N) b[C[pre[i]]].push_back(pre[i]);

  rep(i,N){
    res[i] += (ll)N * (N+1) / 2;
    ind = 0;
    solve(-1, ind, b[i], res[i]);
  }

  wtLn(res(N));
}

Current time: 2024年04月26日11時36分04秒
Last modified: 2020年04月30日02時57分32秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC163 ABC_F
トップページに戻る

Logged in as: unknown user (not login)