test/yukicoder/828.ETT.test.cpp

• View this file on GitHub
• Last update: 2024-10-12 14:04:05+09:00
• Problem: https://yukicoder.me/problems/no/828

Depends on

• Euler-Tour-Tree (src/DataStructure/EulerTourTree.hpp)
• メンバの有無を判定するテンプレート 他 (src/Internal/HAS_CHECK.hpp)

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/828
// competitive-verifier: TLE 1
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include "src/DataStructure/EulerTourTree.hpp"
using namespace std;
struct RaddQ {
 using T= long long;
 using E= long long;
 static void mp(T &t, E e, int sz) { t+= e; }
 static void cp(E &pre, E suf) { pre+= suf; }
};
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 int r[N];
 for (int i= 0; i < N; i++) cin >> r[i];
 EulerTourTree<RaddQ> ett(N);
 vector<int> tree[N];
 for (int i= 0; i < N - 1; i++) {
  int u, v;
  cin >> u >> v;
  u--, v--;
  if (u > v) swap(u, v);
  ett.link(u, v);
  tree[v].push_back(u);
 }
 for (int v= N; v--;) {
  ett.apply_tree(v, 1);
  for (int u: tree[v]) ett.cut(u, v);
 }
 long long ans= 1;
 for (int i= 0; i < N; i++) (ans*= r[i] + ett[i])%= int(1e9 + 7);
 cout << ans << '\n';
 return 0;
}

#line 1 "test/yukicoder/828.ETT.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/828
// competitive-verifier: TLE 1
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#line 2 "src/DataStructure/EulerTourTree.hpp"
#include <algorithm>
#include <string>
#include <unordered_map>
#include <cstddef>
#include <cstdint>
#line 2 "src/Internal/HAS_CHECK.hpp"
#include <type_traits>
#define MEMBER_MACRO(member, Dummy, name, type1, type2, last) \
 template <class tClass> struct name##member { \
  template <class U, Dummy> static type1 check(U *); \
  static type2 check(...); \
  static tClass *mClass; \
  last; \
 }
#define HAS_CHECK(member, Dummy) MEMBER_MACRO(member, Dummy, has_, std::true_type, std::false_type, static const bool value= decltype(check(mClass))::value)
#define HAS_MEMBER(member) HAS_CHECK(member, int dummy= (&U::member, 0))
#define HAS_TYPE(member) HAS_CHECK(member, class dummy= typename U::member)
#define HOGE_OR(member, name, type2) \
 MEMBER_MACRO(member, class dummy= typename U::member, name, typename U::member, type2, using type= decltype(check(mClass))); \
 template <class tClass> using name##member##_t= typename name##member<tClass>::type
#define NULLPTR_OR(member) HOGE_OR(member, nullptr_or_, std::nullptr_t)
#define MYSELF_OR(member) HOGE_OR(member, myself_or_, tClass)
#line 8 "src/DataStructure/EulerTourTree.hpp"
template <typename M= void, size_t NODE_SIZE= 4'000'000> class EulerTourTree {
 HAS_MEMBER(op);
 HAS_MEMBER(ti);
 HAS_MEMBER(mp);
 HAS_MEMBER(cp);
 HAS_TYPE(T);
 HAS_TYPE(E);
 NULLPTR_OR(T);
 NULLPTR_OR(E);
 template <class L> static constexpr bool monoid_v= std::conjunction_v<has_T<L>, has_op<L>, has_ti<L>>;
 template <class L> static constexpr bool dual_v= std::conjunction_v<has_T<L>, has_E<L>, has_mp<L>, has_cp<L>>;
 using node_id= int;
 using vertex_id= int;
 struct Node_B {
  node_id ch[2], par;
  uint64_t flag;
 };
 template <class D, bool mo, bool du> struct Node_D: Node_B {};
 template <class D> struct Node_D<D, 1, 0>: Node_B {
  typename M::T val= M::ti(), sum= M::ti();
 };
 template <class D> struct Node_D<D, 0, 1>: Node_B {
  typename M::T val;
  typename M::E laz;
  bool laz_flg;
 };
 template <class D> struct Node_D<D, 1, 1>: Node_B {
  typename M::T val= M::ti(), sum= M::ti();
  typename M::E laz;
  bool laz_flg;
 };
 using Node= Node_D<void, monoid_v<M>, dual_v<M>>;
public:
 using T= nullptr_or_T_t<M>;
 using E= nullptr_or_E_t<M>;
private:
 static inline Node *n= new Node[NODE_SIZE];
 static inline node_id ni= 1;
 node_id new_edge(int s, int d, bool hi) {
  int i= ni++, ri= ni++;
  n[i].flag= (uint64_t(s) << 44) | (uint64_t(d) << 24) | hi;
  n[ri].flag= (uint64_t(d) << 44) | (uint64_t(s) << 24);
  return i;
 }
 static void update(node_id i) {
  n[i].flag&= 0xffffffffff00000f;
  n[i].flag|= ((n[i].flag >> 44) == ((n[i].flag >> 24) & 0xfffff)) << 4;
  n[i].flag&= -11ll, n[i].flag|= (n[i].flag << 1) & 0b1111;
  if constexpr (monoid_v<M>) n[i].sum= n[i].val;
  if (n[i].ch[0]) {
   n[i].flag+= (n[n[i].ch[0]].flag & 0xfffff0), n[i].flag|= n[n[i].ch[0]].flag & 0b1010;
   if constexpr (monoid_v<M>) n[i].sum= M::op(n[n[i].ch[0]].sum, n[i].sum);
  }
  if (n[i].ch[1]) {
   n[i].flag+= (n[n[i].ch[1]].flag & 0xfffff0), n[i].flag|= n[n[i].ch[1]].flag & 0b1010;
   if constexpr (monoid_v<M>) n[i].sum= M::op(n[i].sum, n[n[i].ch[1]].sum);
  }
 }
 static inline void map(T &v, E x, int sz) {
  if constexpr (std::is_invocable_r_v<void, decltype(M::mp), T &, E, int>) M::mp(v, x, sz);
  else M::mp(v, x);
 }
 static inline void propagate(node_id i, const E &x) {
  if (n[i].laz_flg) M::cp(n[i].laz, x);
  else n[i].laz= x, n[i].laz_flg= true;
  if ((n[i].flag >> 44) == ((n[i].flag >> 24) & 0xfffff)) map(n[i].val, x, 1);
  if constexpr (monoid_v<M>) map(n[i].sum, x, ((n[i].flag >> 4) & 0xfffff));
 }
 static inline void push(node_id i) {
  if (!n[i].laz_flg) return;
  if (n[i].ch[0]) propagate(n[i].ch[0], n[i].laz);
  if (n[i].ch[1]) propagate(n[i].ch[1], n[i].laz);
  n[i].laz_flg= false;
 }
 static inline int dir(node_id i) { return n[n[i].par].ch[1] == i; }
 static inline void rot(node_id i) {
  node_id p= n[i].par;
  int d= dir(i);
  if ((n[p].ch[d]= n[i].ch[!d])) n[n[p].ch[d]].par= p;
  n[i].ch[!d]= p;
  if ((n[i].par= n[p].par)) n[n[p].par].ch[dir(p)]= i;
  n[p].par= i, update(p);
 }
 static inline void splay(node_id i) {
  if constexpr (dual_v<M>) push(i);
  for (node_id p= n[i].par; p; rot(i), p= n[i].par) {
   node_id pp= n[p].par;
   if constexpr (dual_v<M>) {
    if (pp) push(pp);
    push(p), push(i);
   }
   if (pp) rot(dir(i) == dir(p) ? p : i);
  }
  update(i);
 }
 static inline node_id merge_back(node_id l, node_id r) {
  if (!l) return r;
  if (!r) return l;
  while (n[l].ch[1]) l= n[l].ch[1];
  return splay(l), n[n[r].par= l].ch[1]= r, update(l), l;
 }
 static inline std::pair<node_id, node_id> split(node_id i) {
  splay(i);
  node_id l= n[i].ch[0];
  return n[i].ch[0]= n[l].par= 0, update(i), std::make_pair(l, i);
 }
 static inline void reroot(node_id v) {
  auto p= split(v);
  merge_back(p.second, p.first), splay(v);
 }
 static inline bool same_root(node_id i, node_id j) {
  if (i) splay(i);
  if (j) splay(j);
  while (n[i].par) i= n[i].par;
  while (n[j].par) j= n[j].par;
  return i == j;
 }
 node_id n_st;
 std::unordered_map<uint64_t, node_id> emp;
public:
 EulerTourTree() {}
 EulerTourTree(int N): n_st(ni) {
  ni+= N;
  for (int i= 0; i < N; i++) n[i + n_st].flag= 0x100001000000 * i;
 }
 const T &operator[](vertex_id x) { return get(x); }
 const T &get(vertex_id x) {
  static_assert(monoid_v<M> || dual_v<M>, "\"get\" is not available\n");
  return n[x + n_st].val;
 }
 void set(vertex_id x, T val) {
  static_assert(monoid_v<M> || dual_v<M>, "\"set\" is not available\n");
  splay(x+= n_st), n[x].val= val, update(x);
 }
 bool edge_exist(vertex_id x, vertex_id y) {
  if (x > y) std::swap(x, y);
  return emp.count(((long long)x << 32) | y);
 }
 void link(vertex_id x, vertex_id y, bool hi= true) {
  if (x > y) std::swap(x, y);
  int ei= new_edge(x, y, hi);
  emp.insert(std::make_pair(((long long)x << 32) | y, ei));
  x+= n_st, y+= n_st, reroot(x), reroot(y);
  n[n[x].par= ei].ch[0]= x, n[n[y].par= ei].ch[1]= y;
  update(ei), merge_back(ei, ei + 1);
 }
 void cut(vertex_id x, vertex_id y) {
  if (x > y) std::swap(x, y);
  int ei= emp[((long long)x << 32) | y], rei= ei + 1;
  emp.erase(((long long)x << 32) | y);
  auto [pl, pr]= split(ei);
  node_id left, center, right;
  if (pl && same_root(pl, rei)) {
   auto [ql, qr]= split(rei);
   left= ql, center= n[qr].ch[1], right= n[pr].ch[1], n[center].par= 0;
  } else {
   splay(ei), n[ei= n[ei].ch[1]].par= 0;
   auto [ql, qr]= split(rei);
   splay(pl), left= pl, right= n[qr].ch[1];
  }
  n[right].par= 0, merge_back(left, right);
 }
 bool connected(vertex_id x, vertex_id y) { return same_root(x + n_st, y + n_st); }
 void subedge_set(vertex_id x, bool val) {
  splay(x+= n_st);
  if (val) n[x].flag|= 0b0100;
  else n[x].flag&= -5ll;
  update(x);
 }
 size_t tree_size(vertex_id x) { return splay(x+= n_st), ((n[x].flag >> 4) & 0xfffff); }
 T prod_tree(vertex_id x) {
  static_assert(monoid_v<M>, "\"prod\" is not available\n");
  return splay(x+= n_st), n[x].sum;
 }
 T prod_subtree(vertex_id x, vertex_id par= -1) {
  if (par == -1) return prod_tree(x);
  cut(x, par);
  T ret= prod_tree(x);
  link(x, par);
  return ret;
 }
 void apply_tree(vertex_id x, E v) {
  static_assert(dual_v<M>, "\"apply\" is not available\n");
  splay(x+= n_st), propagate(x, v), push(x);
 }
 void apply_subtree(vertex_id x, vertex_id par, E v) { cut(x, par), apply_tree(x, v), link(x, par); }
 static std::string which_available() {
  std::string ret= "";
  if constexpr (monoid_v<M>) ret+= "\"prod\" ";
  if constexpr (dual_v<M>) ret+= "\"apply\" ";
  return ret;
 }
 template <class Func> void hilevel_edges(vertex_id v, Func f) {
  splay(v+= n_st);
  while (v && (n[v].flag & 0b0010))
   while (1) {
    if (n[v].flag & 0b0001) {
     f((n[v].flag >> 44), ((n[v].flag >> 24) & 0xfffff)), splay(v), n[v].flag&= -2ll, update(v);
     break;
    } else v= n[v].ch[!(n[v].ch[0] && (n[n[v].ch[0]].flag & 0b0010))];
   }
 }
 template <class Func> int subedges(vertex_id v, Func f) {
  splay(v+= n_st);
  while (v && (n[v].flag & 0b1000))
   for (bool loop= true; loop;) {
    if (n[v].flag & 0b0100) {
     if (f(n[v].flag >> 44)) return 1;
     splay(v), loop= false;
    } else v= n[v].ch[!(n[v].ch[0] && (n[n[v].ch[0]].flag & 0b1000))];
   }
  return 0;
 }
};
#line 7 "test/yukicoder/828.ETT.test.cpp"
using namespace std;
struct RaddQ {
 using T= long long;
 using E= long long;
 static void mp(T &t, E e, int sz) { t+= e; }
 static void cp(E &pre, E suf) { pre+= suf; }
};
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 int r[N];
 for (int i= 0; i < N; i++) cin >> r[i];
 EulerTourTree<RaddQ> ett(N);
 vector<int> tree[N];
 for (int i= 0; i < N - 1; i++) {
  int u, v;
  cin >> u >> v;
  u--, v--;
  if (u > v) swap(u, v);
  ett.link(u, v);
  tree[v].push_back(u);
 }
 for (int v= N; v--;) {
  ett.apply_tree(v, 1);
  for (int u: tree[v]) ett.cut(u, v);
 }
 long long ans= 1;
 for (int i= 0; i < N; i++) (ans*= r[i] + ett[i])%= int(1e9 + 7);
 cout << ans << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	a_sample_1.txt	AC	6 ms	4 MB
g++-13	a_sample_2.txt	AC	5 ms	4 MB
g++-13	a_sample_3.txt	AC	5 ms	4 MB
g++-13	b_small_1.txt	AC	19 ms	8 MB
g++-13	b_small_10.txt	AC	16 ms	5 MB
g++-13	b_small_2.txt	AC	9 ms	4 MB
g++-13	b_small_3.txt	AC	18 ms	8 MB
g++-13	b_small_4.txt	AC	8 ms	4 MB
g++-13	b_small_5.txt	AC	7 ms	4 MB
g++-13	b_small_6.txt	AC	8 ms	4 MB
g++-13	b_small_7.txt	AC	7 ms	4 MB
g++-13	b_small_8.txt	AC	15 ms	5 MB
g++-13	b_small_9.txt	AC	7 ms	4 MB
g++-13	c_path_1.txt	AC	79 ms	21 MB
g++-13	c_path_10.txt	AC	43 ms	14 MB
g++-13	c_path_2.txt	AC	221 ms	38 MB
g++-13	c_path_3.txt	AC	60 ms	18 MB
g++-13	c_path_4.txt	AC	87 ms	22 MB
g++-13	c_path_5.txt	AC	66 ms	18 MB
g++-13	c_path_6.txt	AC	143 ms	29 MB
g++-13	c_path_7.txt	AC	313 ms	49 MB
g++-13	c_path_8.txt	AC	189 ms	34 MB
g++-13	c_path_9.txt	AC	248 ms	41 MB
g++-13	d_random_1.txt	AC	23 ms	8 MB
g++-13	d_random_10.txt	AC	436 ms	47 MB
g++-13	d_random_11.txt	AC	479 ms	49 MB
g++-13	d_random_12.txt	AC	346 ms	38 MB
g++-13	d_random_13.txt	AC	218 ms	28 MB
g++-13	d_random_14.txt	AC	278 ms	34 MB
g++-13	d_random_15.txt	AC	168 ms	24 MB
g++-13	d_random_16.txt	AC	248 ms	31 MB
g++-13	d_random_17.txt	AC	434 ms	47 MB
g++-13	d_random_18.txt	AC	160 ms	24 MB
g++-13	d_random_19.txt	AC	129 ms	21 MB
g++-13	d_random_2.txt	AC	204 ms	28 MB
g++-13	d_random_20.txt	AC	482 ms	49 MB
g++-13	d_random_3.txt	AC	63 ms	14 MB
g++-13	d_random_4.txt	AC	434 ms	47 MB
g++-13	d_random_5.txt	AC	329 ms	38 MB
g++-13	d_random_6.txt	AC	420 ms	47 MB
g++-13	d_random_7.txt	AC	386 ms	41 MB
g++-13	d_random_8.txt	AC	198 ms	28 MB
g++-13	d_random_9.txt	AC	197 ms	26 MB
g++-13	e_hand_1.txt	AC	81 ms	43 MB
g++-13	e_hand_2.txt	AC	35 ms	19 MB
g++-13	e_hand_3.txt	AC	50 ms	27 MB
clang++-18	a_sample_1.txt	AC	6 ms	4 MB
clang++-18	a_sample_2.txt	AC	6 ms	4 MB
clang++-18	a_sample_3.txt	AC	5 ms	4 MB
clang++-18	b_small_1.txt	AC	20 ms	8 MB
clang++-18	b_small_10.txt	AC	16 ms	5 MB
clang++-18	b_small_2.txt	AC	9 ms	4 MB
clang++-18	b_small_3.txt	AC	19 ms	8 MB
clang++-18	b_small_4.txt	AC	9 ms	4 MB
clang++-18	b_small_5.txt	AC	7 ms	4 MB
clang++-18	b_small_6.txt	AC	8 ms	4 MB
clang++-18	b_small_7.txt	AC	7 ms	4 MB
clang++-18	b_small_8.txt	AC	16 ms	5 MB
clang++-18	b_small_9.txt	AC	7 ms	4 MB
clang++-18	c_path_1.txt	AC	89 ms	21 MB
clang++-18	c_path_10.txt	AC	45 ms	14 MB
clang++-18	c_path_2.txt	AC	232 ms	38 MB
clang++-18	c_path_3.txt	AC	63 ms	18 MB
clang++-18	c_path_4.txt	AC	93 ms	22 MB
clang++-18	c_path_5.txt	AC	69 ms	18 MB
clang++-18	c_path_6.txt	AC	152 ms	29 MB
clang++-18	c_path_7.txt	AC	313 ms	49 MB
clang++-18	c_path_8.txt	AC	188 ms	34 MB
clang++-18	c_path_9.txt	AC	257 ms	41 MB
clang++-18	d_random_1.txt	AC	24 ms	8 MB
clang++-18	d_random_10.txt	AC	454 ms	47 MB
clang++-18	d_random_11.txt	AC	475 ms	49 MB
clang++-18	d_random_12.txt	AC	358 ms	38 MB
clang++-18	d_random_13.txt	AC	221 ms	28 MB
clang++-18	d_random_14.txt	AC	285 ms	34 MB
clang++-18	d_random_15.txt	AC	173 ms	24 MB
clang++-18	d_random_16.txt	AC	246 ms	31 MB
clang++-18	d_random_17.txt	AC	449 ms	47 MB
clang++-18	d_random_18.txt	AC	168 ms	24 MB
clang++-18	d_random_19.txt	AC	129 ms	21 MB
clang++-18	d_random_2.txt	AC	206 ms	28 MB
clang++-18	d_random_20.txt	AC	474 ms	49 MB
clang++-18	d_random_3.txt	AC	68 ms	14 MB
clang++-18	d_random_4.txt	AC	448 ms	47 MB
clang++-18	d_random_5.txt	AC	367 ms	38 MB
clang++-18	d_random_6.txt	AC	453 ms	47 MB
clang++-18	d_random_7.txt	AC	414 ms	41 MB
clang++-18	d_random_8.txt	AC	213 ms	28 MB
clang++-18	d_random_9.txt	AC	206 ms	26 MB
clang++-18	e_hand_1.txt	AC	76 ms	43 MB
clang++-18	e_hand_2.txt	AC	34 ms	19 MB
clang++-18	e_hand_3.txt	AC	48 ms	27 MB

Back to top page