保存されている過去のバージョンの一覧

2021年05月21日20時47分13秒

Codeforces Round #721 DIV2 D問題 - MEX Tree

Source

Codeforces Round #721 DIV2 D問題 (2250pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20210405-1）のコード

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

//no-unlocked
int N, A[2d5], B[2d5];
graph g;
HLD hld;
ll res[2d5+1];
int sz[];
{
  REP(rd_int()){
    int x = 0, y = 0, z, fg;
    rd(N,(A,B)(N-1));
    g.setEdge(N,N-1,A,B);
    hld.init(g);
    rep(i,N+1) res[i] = 0;
    g.SubTreeSize(0,sz);
    rep[g.edge[0]](i,g.es[0]) res[0] += (ll)sz[i]*(sz[i]-1)/2;
    res[1] = (ll) N * (N-1) / 2 - res[0];
    rep(i,1,N){
      fg = 0;
      if(fg == 0 && abs(hld.depth(x) - hld.depth(i)) == hld.dist(x,i)){
        fg = 1;
        if(hld.depth(x) < hld.depth(i)) x = i;
      }
      if(fg == 0 && abs(hld.depth(y) - hld.depth(i)) == hld.dist(y,i)){
        fg = 1;
        if(hld.depth(y) < hld.depth(i)) y = i;
      }
      if(!fg || hld.lca(x,y) != 0) break;

      if(y == 0){
        z = hld.up(x, hld.depth(x)-1);
        res[i+1] = (ll)sz[x] * (N-sz[z]);
      } else {
        res[i+1] = (ll)sz[x] * sz[y];
      }
      res[i] -= res[i+1];
    }
    wt(res(N+1));
  }
}

Current time: 2024年04月20日19時54分54秒
Last modified: 2021年05月21日20時47分13秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF721 CF_DIV2_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン：