Top Tree

[ei1333]

https://ei1333.github.io/library/structure/develop/super-link-cut-tree.hpp の抽象化がカスなのでなんとかできないか調査する

[ei1333]

https://yukicoder.me/submissions/977729 Nyaan さんありがとう

[ei1333]

https://judge.yosupo.jp/submission/205578

[ei1333]

Super Link Cut Tree は適切に書き換えることにより、vertex、add_vertex、compress、rake、add_edgeの5つの演算に書き換え可能

[ei1333]

AOJ 2450

as is

// 遅延伝搬をする作用素
struct Lazy {
  int v;

  // 単位元
  Lazy() : v{inf} {}

  // 初期化
  Lazy(int v) : v{v} {}

  void propagate(const Lazy &p) {
    if(p.v != inf) v = p.v;
  }
};

// Light-edge の情報
template< typename Lazy >
struct LInfo {

  // 単位元(キーの値はアクセスしないので未初期化でもよい
  LInfo() {}

  // 初期化
  LInfo(T v) {}

  // l, r は Splay-tree の子 (原理上、各ノード区別はない)
  void update(const LInfo &l, const LInfo &r) {}

  // 部分木への遅延伝搬
  void propagate(const Lazy &p) {}
};

// Heavy-edge の情報
template< typename LInfo, typename Lazy >
struct Info {
  T v;

  T dp, dp_p, dp_c, all;
  int sz;

  // 単位元(キーの値はアクセスしないので未初期化でもよい
  Info() : dp{-infll}, dp_p{-infll}, dp_c{-infll}, all{0}, sz{0} {}

  // 初期化
  Info(T v) : v{v} {}

  // 反転
  void toggle() { swap(dp_p, dp_c); }

  // pが親, cがheavy-edgeで結ばれた子, lがそれ以外の子
  void update(const Info &p, const Info &c, const LInfo &l) {
    all = p.all + v + c.all;
    sz = p.sz + 1 + c.sz;

    dp = max({p.dp, c.dp, max< T >(0, p.dp_c) + v + max< T >(0, c.dp_p)});
    dp_p = max(p.dp_p, p.all + v + max< T >(0, c.dp_p));
    dp_c = max(c.dp_c, c.all + v + max< T >(0, p.dp_c));
  }

  // 親と light-edge で繋げる
  LInfo link() const { return LInfo(); }

  // 遅延伝搬
  void propagate(const Lazy &p) {
    if(p.v != inf) {
      v = p.v;
      all = v * sz;
      dp = dp_c = dp_p = max(v, all);
    }
  }

  // light-edgeに対する遅延伝搬
  // 基本的にはpropagateのみ実装すれば十分
  // pathとsubtreeの遅延伝搬が両方ある場合を除く
  void propagate_light(const Lazy &p) {}
};

to be: dp_p, dp_c の両方向を LCT 内部で持つためちょっと楽かも（方向の区別のない変数は2つ余分に持つことになる）

struct TreeDPInfo {
  struct Lazy {
    int v;
    Lazy() : v{inf} {}
    explicit Lazy(int v): v{v} {}
    void propagate(const Lazy &p) {
      if(p.v != inf) v = p.v;
    }
  };
  struct Point {
    void propagate(const Lazy &p) {
    }
  };
  struct Path {
    int ans, all, suf, pref, sz;
    void propagate(const Lazy& p) {
      if(p.v != inf) {
        all = p.v * sz;
        ans = suf = pref = max(p.v, all);
      }
    }
    void propagate_light(const Lazy& p) {
    }
  };
  struct Info {
    int v;
    void propagate(const Lazy& p) {
      if(p.v != inf) v = p.v;
    }
  };

  static Path vertex(const Info& u) {
    return {u.v, u.v, u.v, u.v, 1};
  }
  static Path add_vertex(const Point& d, const Info& u) {
    return {u.v, u.v, u.v, u.v, 1};
  }
  static Point add_edge(const Path& d) {
    return {};
  }
  static Point rake(const Point& l, const Point& r) {
    return {};
  }
  static Path compress(const Path& p, const Path& c) {
    return {max({p.ans, c.ans, p.suf + c.pref}), p.all + c.all, max(c.suf, p.suf + c.all), max(p.pref, c.pref + p.all), p.sz + c.sz};
  }
};

[ei1333]

https://github.com/ei1333/library/tree/c65c9e7961d1d123411bb309c46bca9e95ee8bf6/structure/develop と https://github.com/ei1333/library/tree/c65c9e7961d1d123411bb309c46bca9e95ee8bf6/structure/lct は消していいので気が向いたら消す