東京工業大学プログラミングコンテスト2019 M問題 - Inversion Numbers of Tree

Source

東京工業大学プログラミングコンテスト2019
問題文

問題概要

省略

解法

省略

cLayversion 20190830-1)のコード

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

int N, A[2d5], B[2d5];

ll c[2d5];
int *es, **edge;
ll **dp;

int up[1d5];
ll res[1d5];
fenwick<int> f;

ll dfs1(int n, int b){
  int i, k, t, u;
  ll r = 0, tmp;

  f.add(n,1);
  up[n] = n;

  rep(i,es[n]){
    k = edge[n][i];
    if(k==b) continue;

    t = f.get(n);
    tmp = dfs1(k,n);
    tmp += (u = f.get(n) - t);
    r += (dp[n][i] = tmp);
    up[n] -= u;
  }

  return res[n] = r;
}

void dfs2(int n, int b, ll v){
  int i, k;

  if(b >= 0) res[n] += res[b] - v + up[n];

  rep(i,es[n]){
    k = edge[n][i];
    if(k==b) continue;
    dfs2(k,n,dp[n][i]);
  }
}

{
  rd(N,(A--,B--)(N-1));
  rep(i,N-1) A[N-1+i] = B[i];
  rep(i,N-1) B[N-1+i] = A[i];
  wAdjEdge(N, 2*(N-1), A, B, c, &es, &edge, &dp);

  f.walloc(N);
  f.init(N);
  dfs1(0, -1);
  dfs2(0, -1, 0);

  wtLn(res(N));
}


Current time: 2021年09月24日23時37分40秒
Last modified: 2019年09月01日00時50分54秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: