test/aoj/2450.LCT.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 12:11:12+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/challenges/sources/JAG/Summer/2450

Depends on

• Link-Cut-Tree (src/DataStructure/LinkCutTree.hpp)
• detection idiom (src/Internal/detection_idiom.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/challenges/sources/JAG/Summer/2450
// competitive-verifier: TLE 1
// competitive-verifier: MLE 64
// Do use segment tree
#include <iostream>
#include <algorithm>
#include "src/DataStructure/LinkCutTree.hpp"
using namespace std;
struct RupdQ_RmaxsumQ {
 struct T {
  long long sum, max, lmax, rmax;
  int size;
 };
 using E= long long;
 static T op(const T &a, const T &b) {
  T ret;
  ret.sum= a.sum + b.sum;
  ret.max= max({a.max, b.max, a.rmax + b.lmax});
  ret.lmax= max(a.lmax, a.sum + b.lmax);
  ret.rmax= max(a.rmax + b.sum, b.rmax);
  ret.size= a.size + b.size;
  return ret;
 }
 static void mp(T &v, const E &f) {
  v.sum= f * v.size;
  v.max= v.lmax= v.rmax= max(v.sum, f);
 }
 static void cp(E &pre, const E &suf) { pre= suf; }
};
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 LinkCutTree<RupdQ_RmaxsumQ> lct(N);
 for (int i= 0; i < N; ++i) {
  long long w;
  cin >> w;
  lct.set(i, {w, w, w, w, 1});
 }
 for (int i= 0; i < N - 1; i++) {
  int u, v;
  cin >> u >> v;
  lct.link(--u, --v);
 }
 while (Q--) {
  long long t, a, b, c;
  cin >> t >> a >> b >> c, --a, --b;
  if (t == 1) lct.apply(a, b, c);
  else cout << lct.prod(a, b).max << '\n';
 }
 return 0;
}

#line 1 "test/aoj/2450.LCT.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/challenges/sources/JAG/Summer/2450
// competitive-verifier: TLE 1
// competitive-verifier: MLE 64
// Do use segment tree
#include <iostream>
#include <algorithm>
#line 3 "src/DataStructure/LinkCutTree.hpp"
#include <vector>
#include <string>
#include <cstddef>
#include <utility>
#include <cassert>
#line 2 "src/Internal/detection_idiom.hpp"
#include <type_traits>
#define _DETECT_BOOL(name, ...) \
 template <class, class= void> struct name: std::false_type {}; \
 template <class T> struct name<T, std::void_t<__VA_ARGS__>>: std::true_type {}; \
 template <class T> static constexpr bool name##_v= name<T>::value
#define _DETECT_TYPE(name, type1, type2, ...) \
 template <class T, class= void> struct name { \
  using type= type2; \
 }; \
 template <class T> struct name<T, std::void_t<__VA_ARGS__>> { \
  using type= type1; \
 }
#line 9 "src/DataStructure/LinkCutTree.hpp"
template <class M= void> class LinkCutTree {
 _DETECT_BOOL(semigroup, typename T::T, decltype(&T::op));
 _DETECT_BOOL(dual, typename T::T, typename T::E, decltype(&T::mp), decltype(&T::cp));
 _DETECT_BOOL(commute, typename T::commute);
 _DETECT_TYPE(myself_or_T, typename T::T, T, typename T::T);
 _DETECT_TYPE(nullptr_or_E, typename T::E, std::nullptr_t, typename T::E);
 using T= std::conditional_t<std::is_void_v<M>, std::nullptr_t, typename myself_or_T<M>::type>;
 using E= typename nullptr_or_E<M>::type;
 struct NodeB {
  int ch[2]= {-1, -1}, par= -1;
  bool revf= 0;
 };
 template <class D, class A> struct NodeV: NodeB {
  T val;
 };
 template <class D> struct NodeV<D, void>: NodeB {};
 template <class D, bool du> struct NodeD: NodeV<D, M> {};
 template <class D> struct NodeD<D, 1>: NodeV<D, M> {
  E laz;
  bool lazf= 0;
 };
 template <class D, bool sg, bool com> struct NodeS: NodeD<D, dual_v<M>> {};
 template <class D> struct NodeS<D, 1, 1>: NodeD<D, dual_v<M>> {
  T sum;
 };
 template <class D> struct NodeS<D, 1, 0>: NodeD<D, dual_v<M>> {
  T sum, rsum;
 };
 using Node= NodeS<void, semigroup_v<M>, commute_v<M>>;
 std::vector<Node> n;
 inline void update(int i) {
  n[i].sum= n[i].val;
  if constexpr (!commute_v<M>) n[i].rsum= n[i].val;
  if (int l= n[i].ch[0]; l != -1) {
   n[i].sum= M::op(n[l].sum, n[i].sum);
   if constexpr (!commute_v<M>) n[i].rsum= M::op(n[i].rsum, n[l].rsum);
  }
  if (int r= n[i].ch[1]; r != -1) {
   n[i].sum= M::op(n[i].sum, n[r].sum);
   if constexpr (!commute_v<M>) n[i].rsum= M::op(n[r].rsum, n[i].rsum);
  }
 }
 inline void propagate(int i, const E &x) {
  if (i == -1) return;
  if (n[i].lazf) M::cp(n[i].laz, x);
  else n[i].laz= x;
  if constexpr (semigroup_v<M>) {
   M::mp(n[i].sum, x);
   if constexpr (!commute_v<M>) M::mp(n[i].rsum, x);
  }
  M::mp(n[i].val, x), n[i].lazf= 1;
 }
 inline void toggle(int i) {
  if (i == -1) return;
  std::swap(n[i].ch[0], n[i].ch[1]);
  if constexpr (semigroup_v<M> && !commute_v<M>) std::swap(n[i].sum, n[i].rsum);
  n[i].revf^= 1;
 }
 inline void push(int i) {
  if (n[i].revf) toggle(n[i].ch[0]), toggle(n[i].ch[1]), n[i].revf= 0;
  if constexpr (dual_v<M>)
   if (n[i].lazf) propagate(n[i].ch[0], n[i].laz), propagate(n[i].ch[1], n[i].laz), n[i].lazf= 0;
 }
 inline int dir(int i) {
  if (int p= n[i].par; p != -1) {
   if (n[p].ch[0] == i) return 0;
   if (n[p].ch[1] == i) return 1;
  }
  return 2;
 }
 inline void rot(int i) {
  int p= n[i].par, d= n[p].ch[1] == i;
  if (int c= n[p].ch[d]= std::exchange(n[i].ch[!d], p); c != -1) n[c].par= p;
  if (d= dir(p); d < 2) n[n[p].par].ch[d]= i;
  n[i].par= std::exchange(n[p].par, i);
  if constexpr (semigroup_v<M>) update(p);
 }
 inline void splay(int i) {
  push(i);
  for (int d; d= dir(i), d < 2; rot(i))
   if (int p= n[i].par, c= dir(p), pp= n[p].par; c < 2) push(pp), push(p), push(i), rot(d == c ? p : i);
   else push(p), push(i);
  if constexpr (semigroup_v<M>) update(i);
 }
 inline int expose(int i) {
  int r= -1;
  for (int p= i; p != -1; r= p, p= n[p].par) {
   splay(p), n[p].ch[1]= r;
   if constexpr (semigroup_v<M>) update(p);
  }
  return splay(i), r;
 }
public:
 LinkCutTree(size_t sz): n(sz) {}
 LinkCutTree(size_t sz, T val): n(sz) {
  for (int i= sz; i--;) n[i].val= val;
 }
 void evert(int k) { expose(k), toggle(k), push(k); }
 void link(int c, int p) {
  evert(c), expose(p), assert(n[c].par == -1), n[p].ch[1]= c, n[c].par= p;
  if constexpr (semigroup_v<M>) update(p);
 }
 void cut(int c, int p) {
  evert(p), expose(c), assert(n[c].ch[0] == p), n[c].ch[0]= n[p].par= -1;
  if constexpr (semigroup_v<M>) update(c);
 }
 int root(int x) {
  for (expose(x);; x= n[x].ch[0])
   if (push(x), n[x].ch[0] == -1) return splay(x), x;
 }
 int parent(int x) {
  if (expose(x), x= n[x].ch[0]; x == -1) return -1;
  for (;; x= n[x].ch[1])
   if (push(x), n[x].ch[1] == -1) return splay(x), x;
 }
 int lca(int x, int y) { return x == y ? x : (expose(x), y= expose(y), n[x].par == -1) ? -1 : y; }
 const T &get(int k) {
  static_assert(!std::is_void_v<M>, "\"get\" is not available\n");
  return expose(k), n[k].val;
 }
 T &at(int k) {
  static_assert(!std::is_void_v<M> && !semigroup_v<M>, "\"at\" is not available\n");
  return expose(k), n[k].val;
 }
 template <class L= M> const std::enable_if_t<semigroup_v<L>, T> &operator[](size_t k) { return get(k); }
 template <class L= M> std::enable_if_t<!semigroup_v<L>, T> &operator[](size_t k) { return at(k); }
 void set(int k, const T &v) {
  static_assert(!std::is_void_v<M>, "\"set\" is not available\n");
  expose(k), n[k].val= v;
  if constexpr (semigroup_v<M>) update(k);
 }
 void mul(int k, const T &v) {
  static_assert(semigroup_v<M> && commute_v<M>, "\"mul\" is not available\n");
  expose(k), n[k].val= M::op(n[k].val, v), update(k);
 }
 // [a,b] closed section
 T prod(int a, int b) {
  static_assert(semigroup_v<M>, "\"prod\" is not available\n");
  return a == b ? get(a) : (evert(a), expose(b), assert(n[a].par != -1), n[b].sum);
 }
 // [a,b] closed section
 void apply(int a, int b, const E &v) {
  static_assert(dual_v<M>, "\"apply\" is not available\n");
  evert(a), expose(b), assert(a == b || n[a].par != -1), propagate(b, v), push(b);
 }
 static std::string which_unavailable() {
  std::string ret= "";
  if constexpr (semigroup_v<M>) ret+= "\"at\" ";
  else ret+= "\"prod\" ";
  if constexpr (!semigroup_v<M> || !commute_v<M>) ret+= "\"mul\" ";
  if constexpr (!dual_v<M>) ret+= "\"apply\" ";
  if constexpr (std::is_void_v<M>) ret+= "\"get\" \"set\" ";
  return ret;
 }
};
#line 8 "test/aoj/2450.LCT.test.cpp"
using namespace std;
struct RupdQ_RmaxsumQ {
 struct T {
  long long sum, max, lmax, rmax;
  int size;
 };
 using E= long long;
 static T op(const T &a, const T &b) {
  T ret;
  ret.sum= a.sum + b.sum;
  ret.max= max({a.max, b.max, a.rmax + b.lmax});
  ret.lmax= max(a.lmax, a.sum + b.lmax);
  ret.rmax= max(a.rmax + b.sum, b.rmax);
  ret.size= a.size + b.size;
  return ret;
 }
 static void mp(T &v, const E &f) {
  v.sum= f * v.size;
  v.max= v.lmax= v.rmax= max(v.sum, f);
 }
 static void cp(E &pre, const E &suf) { pre= suf; }
};
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 LinkCutTree<RupdQ_RmaxsumQ> lct(N);
 for (int i= 0; i < N; ++i) {
  long long w;
  cin >> w;
  lct.set(i, {w, w, w, w, 1});
 }
 for (int i= 0; i < N - 1; i++) {
  int u, v;
  cin >> u >> v;
  lct.link(--u, --v);
 }
 while (Q--) {
  long long t, a, b, c;
  cin >> t >> a >> b >> c, --a, --b;
  if (t == 1) lct.apply(a, b, c);
  else cout << lct.prod(a, b).max << '\n';
 }
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	testcase_00	AC	5 ms	4 MB
g++-13	testcase_01	AC	5 ms	4 MB
g++-13	testcase_02	AC	5 ms	3 MB
g++-13	testcase_03	AC	5 ms	4 MB
g++-13	testcase_04	AC	5 ms	4 MB
g++-13	testcase_05	AC	238 ms	6 MB
g++-13	testcase_06	AC	317 ms	18 MB
g++-13	testcase_07	AC	428 ms	33 MB
g++-13	testcase_08	AC	6 ms	4 MB
g++-13	testcase_09	AC	15 ms	4 MB
g++-13	testcase_10	AC	122 ms	33 MB
g++-13	testcase_11	AC	6 ms	4 MB
g++-13	testcase_12	AC	5 ms	3 MB
g++-13	testcase_13	AC	5 ms	4 MB
g++-13	testcase_14	AC	8 ms	4 MB
g++-13	testcase_15	AC	30 ms	4 MB
g++-13	testcase_16	AC	160 ms	5 MB
g++-13	testcase_17	AC	247 ms	11 MB
g++-13	testcase_18	AC	290 ms	18 MB
g++-13	testcase_19	AC	391 ms	33 MB
g++-13	testcase_20	AC	6 ms	4 MB
g++-13	testcase_21	AC	6 ms	4 MB
g++-13	testcase_22	AC	14 ms	4 MB
g++-13	testcase_23	AC	96 ms	4 MB
g++-13	testcase_24	AC	284 ms	15 MB
g++-13	testcase_25	AC	338 ms	33 MB
g++-13	testcase_26	AC	6 ms	4 MB
g++-13	testcase_27	AC	215 ms	6 MB
g++-13	testcase_28	AC	289 ms	18 MB
g++-13	testcase_29	AC	393 ms	33 MB
g++-13	testcase_30	AC	6 ms	4 MB
g++-13	testcase_31	AC	8 ms	4 MB
g++-13	testcase_32	AC	39 ms	4 MB
g++-13	testcase_33	AC	182 ms	8 MB
g++-13	testcase_34	AC	224 ms	18 MB
g++-13	testcase_35	AC	307 ms	32 MB
g++-13	testcase_36	AC	305 ms	32 MB
g++-13	testcase_37	AC	310 ms	33 MB
g++-13	testcase_38	AC	304 ms	33 MB
clang++-18	testcase_00	AC	5 ms	4 MB
clang++-18	testcase_01	AC	5 ms	4 MB
clang++-18	testcase_02	AC	5 ms	4 MB
clang++-18	testcase_03	AC	5 ms	4 MB
clang++-18	testcase_04	AC	6 ms	4 MB
clang++-18	testcase_05	AC	242 ms	6 MB
clang++-18	testcase_06	AC	324 ms	18 MB
clang++-18	testcase_07	AC	454 ms	33 MB
clang++-18	testcase_08	AC	6 ms	4 MB
clang++-18	testcase_09	AC	16 ms	4 MB
clang++-18	testcase_10	AC	126 ms	33 MB
clang++-18	testcase_11	AC	6 ms	4 MB
clang++-18	testcase_12	AC	5 ms	4 MB
clang++-18	testcase_13	AC	6 ms	4 MB
clang++-18	testcase_14	AC	8 ms	4 MB
clang++-18	testcase_15	AC	30 ms	4 MB
clang++-18	testcase_16	AC	162 ms	5 MB
clang++-18	testcase_17	AC	249 ms	11 MB
clang++-18	testcase_18	AC	297 ms	18 MB
clang++-18	testcase_19	AC	417 ms	33 MB
clang++-18	testcase_20	AC	6 ms	4 MB
clang++-18	testcase_21	AC	5 ms	4 MB
clang++-18	testcase_22	AC	14 ms	4 MB
clang++-18	testcase_23	AC	106 ms	4 MB
clang++-18	testcase_24	AC	288 ms	15 MB
clang++-18	testcase_25	AC	351 ms	33 MB
clang++-18	testcase_26	AC	6 ms	4 MB
clang++-18	testcase_27	AC	218 ms	6 MB
clang++-18	testcase_28	AC	294 ms	18 MB
clang++-18	testcase_29	AC	389 ms	33 MB
clang++-18	testcase_30	AC	6 ms	4 MB
clang++-18	testcase_31	AC	7 ms	4 MB
clang++-18	testcase_32	AC	40 ms	4 MB
clang++-18	testcase_33	AC	184 ms	8 MB
clang++-18	testcase_34	AC	227 ms	18 MB
clang++-18	testcase_35	AC	292 ms	32 MB
clang++-18	testcase_36	AC	302 ms	32 MB
clang++-18	testcase_37	AC	292 ms	33 MB
clang++-18	testcase_38	AC	296 ms	33 MB

Back to top page