src/ds/dsu/w/lib.hpp - GCC Code Coverage Report

Directory:	./
Coverage:	low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%

Directory:

Coverage:

low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%

	Coverage	Exec / Excl / Total
Lines:	100.0%	221 / 0 / 221
Functions:	100.0%	78 / 0 / 78
Branches:	100.0%	78 / 0 / 78

Coverage

Exec / Excl / Total

Lines:

100.0%

221 / 0 / 221

Functions:

100.0%

78 / 0 / 78

Branches:

100.0%

78 / 0 / 78

    src/ds/dsu/w/lib.hpp
    
        Line
        Branch
        Exec
        Source
      
        #pragma once
      
        #include "../../../util/alias/others/lib.hpp"
      
        namespace tifa_libs {
      
        //! T should be a group with op and inv
      
        template <class T = i64, auto op = std::plus<>{}, auto inv = std::negate<>{}>
      
        requires requires(T x, T y) {
      
          { op(x, y) } -> std::same_as<T>;
      
          { inv(x) } -> std::same_as<T>;
      
        }
      
        class dsu_weighted {
      
          const T E;
      
          veci p;
      
          vec<T> val;  // $a_{root}^{-1}a_i$
      
         public:
      
        720
          CEXPE dsu_weighted(u32 n, cT_(T) E = T{}) NE : E{E}, p(n, -1), val(n, E) {}
      
        157834527
          CEXP i32 find(u32 x) NE {
      
          26/26tifa_libs::dsu_weighted<long, std::plus<void>{}, std::negate<void>{}>::find(unsigned int):
✓ Branch 1 taken 4231886 times.
✓ Branch 2 taken 2459407 times.
tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > > const&))>::find(unsigned int):
✓ Branch 1 taken 8460868 times.
✓ Branch 2 taken 4134004 times.
tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&))>::find(unsigned int):
✓ Branch 1 taken 8460868 times.
✓ Branch 2 taken 4134004 times.
tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > > const&))>::find(unsigned int):
✓ Branch 1 taken 8460868 times.
✓ Branch 2 taken 4134004 times.
tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > > const&))>::find(unsigned int):
✓ Branch 1 taken 8460868 times.
✓ Branch 2 taken 4134004 times.
tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&))>::find(unsigned int):
✓ Branch 1 taken 8460868 times.
✓ Branch 2 taken 4134004 times.
tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&))>::find(unsigned int):
✓ Branch 1 taken 8460868 times.
✓ Branch 2 taken 4134004 times.
tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<11l> >, std::plus<void>{}, std::negate<void>{}>::find(unsigned int):
✓ Branch 1 taken 8460346 times.
✓ Branch 2 taken 4135321 times.
tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, std::plus<void>{}, std::negate<void>{}>::find(unsigned int):
✓ Branch 1 taken 8460346 times.
✓ Branch 2 taken 4135321 times.
tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<11l> >, std::plus<void>{}, std::negate<void>{}>::find(unsigned int):
✓ Branch 1 taken 8460346 times.
✓ Branch 2 taken 4135321 times.
tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<11l> >, std::plus<void>{}, std::negate<void>{}>::find(unsigned int):
✓ Branch 1 taken 8460346 times.
✓ Branch 2 taken 4135321 times.
tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, std::plus<void>{}, std::negate<void>{}>::find(unsigned int):
✓ Branch 1 taken 8460346 times.
✓ Branch 2 taken 4135321 times.
tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, std::plus<void>{}, std::negate<void>{}>::find(unsigned int):
✓ Branch 1 taken 8460346 times.
✓ Branch 2 taken 4135321 times.

        157834527
            if (p[x] < 0) return (i32)x;
      
        52075357
            const auto _ = find((u32)p[x]);
      
        52075357
            val[x] = op(val[(u32)p[x]], val[x]), p[x] = _;
      
        52075357
            return _;
      
          }
      
          ND CEXP u32 size() CNE { return (u32)p.size(); }
      
          CEXP u32 size(u32 x) NE { return (u32)-p[(u32)find(x)]; }
      
        44515648
          CEXP T CR weight(u32 x) NE {
      
        44515648
            find(x);
      
        44515648
            return val[x];
      
          }
      
          // $a_y^{-1}a_x$
      
        3695027
          CEXP T diff(u32 x, u32 y) NE { return op(inv(weight(y)), weight(x)); }
      
        12058964
          CEXP bool same(u32 x, u32 y) NE { return find(x) == find(y); }
      
        18562797
          CEXP bool merge(u32 x, u32 y, T w) NE {
      
        18562797
            w = op(weight(x), inv(op(weight(y), w)));
      
          26/26tifa_libs::dsu_weighted<long, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, long):
✓ Branch 2 taken 77751 times.
✓ Branch 3 taken 585126 times.
tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > >):
✓ Branch 2 taken 157423 times.
✓ Branch 3 taken 1334113 times.
tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >):
✓ Branch 2 taken 157423 times.
✓ Branch 3 taken 1334113 times.
tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > >):
✓ Branch 2 taken 157423 times.
✓ Branch 3 taken 1334113 times.
tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > >):
✓ Branch 2 taken 157423 times.
✓ Branch 3 taken 1334113 times.
tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >):
✓ Branch 2 taken 157423 times.
✓ Branch 3 taken 1334113 times.
tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >):
✓ Branch 2 taken 157423 times.
✓ Branch 3 taken 1334113 times.
tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<11l> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<11l> >):
✓ Branch 2 taken 157633 times.
✓ Branch 3 taken 1334151 times.
tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >):
✓ Branch 2 taken 157633 times.
✓ Branch 3 taken 1334151 times.
tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<11l> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<11l> >):
✓ Branch 2 taken 157633 times.
✓ Branch 3 taken 1334151 times.
tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<11l> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<11l> >):
✓ Branch 2 taken 157633 times.
✓ Branch 3 taken 1334151 times.
tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >):
✓ Branch 2 taken 157633 times.
✓ Branch 3 taken 1334151 times.
tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >):
✓ Branch 2 taken 157633 times.
✓ Branch 3 taken 1334151 times.

        18562797
            if ((x = (u32)find(x)) == (y = (u32)find(y))) return w == E;
      
          26/26tifa_libs::dsu_weighted<long, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, long):
✓ Branch 2 taken 119418 times.
✓ Branch 3 taken 465708 times.
tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > >):
✓ Branch 2 taken 534506 times.
✓ Branch 3 taken 799607 times.
tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >):
✓ Branch 2 taken 534506 times.
✓ Branch 3 taken 799607 times.
tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > >):
✓ Branch 2 taken 534506 times.
✓ Branch 3 taken 799607 times.
tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > >):
✓ Branch 2 taken 534506 times.
✓ Branch 3 taken 799607 times.
tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >):
✓ Branch 2 taken 534506 times.
✓ Branch 3 taken 799607 times.
tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >):
✓ Branch 2 taken 534506 times.
✓ Branch 3 taken 799607 times.
tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<11l> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<11l> >):
✓ Branch 2 taken 535473 times.
✓ Branch 3 taken 798678 times.
tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >):
✓ Branch 2 taken 535473 times.
✓ Branch 3 taken 798678 times.
tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<11l> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<11l> >):
✓ Branch 2 taken 535473 times.
✓ Branch 3 taken 798678 times.
tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<11l> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<11l> >):
✓ Branch 2 taken 535473 times.
✓ Branch 3 taken 798678 times.
tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >):
✓ Branch 2 taken 535473 times.
✓ Branch 3 taken 798678 times.
tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >):
✓ Branch 2 taken 535473 times.
✓ Branch 3 taken 798678 times.

        16594710
            if (p[x] > p[y]) swap(x, y), w = inv(w);
      
        16594710
            p[x] += p[y], p[y] = (i32)x, val[y] = w;
      
        16594710
            return true;
      
          }
      
        };
      
        }  // namespace tifa_libs

Line	Branch	Exec	Source
1			#pragma once
2
3			#include "../../../util/alias/others/lib.hpp"
4
5			namespace tifa_libs {
6
7			//! T should be a group with op and inv
8			template <class T = i64, auto op = std::plus<>{}, auto inv = std::negate<>{}>
9			requires requires(T x, T y) {
10			{ op(x, y) } -> std::same_as<T>;
11			{ inv(x) } -> std::same_as<T>;
12			}
13			class dsu_weighted {
14			const T E;
15			veci p;
16			vec<T> val; // $a_{root}^{-1}a_i$
17
18			public:
19		720	CEXPE dsu_weighted(u32 n, cT_(T) E = T{}) NE : E{E}, p(n, -1), val(n, E) {}
20
21		157834527	CEXP i32 find(u32 x) NE {
22	26/26 tifa_libs::dsu_weighted<long, std::plus<void>{}, std::negate<void>{}>::find(unsigned int): ✓ Branch 1 taken 4231886 times. ✓ Branch 2 taken 2459407 times. tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > > const&))>::find(unsigned int): ✓ Branch 1 taken 8460868 times. ✓ Branch 2 taken 4134004 times. tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&))>::find(unsigned int): ✓ Branch 1 taken 8460868 times. ✓ Branch 2 taken 4134004 times. tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > > const&))>::find(unsigned int): ✓ Branch 1 taken 8460868 times. ✓ Branch 2 taken 4134004 times. tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > > const&))>::find(unsigned int): ✓ Branch 1 taken 8460868 times. ✓ Branch 2 taken 4134004 times. tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&))>::find(unsigned int): ✓ Branch 1 taken 8460868 times. ✓ Branch 2 taken 4134004 times. tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&))>::find(unsigned int): ✓ Branch 1 taken 8460868 times. ✓ Branch 2 taken 4134004 times. tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<11l> >, std::plus<void>{}, std::negate<void>{}>::find(unsigned int): ✓ Branch 1 taken 8460346 times. ✓ Branch 2 taken 4135321 times. tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, std::plus<void>{}, std::negate<void>{}>::find(unsigned int): ✓ Branch 1 taken 8460346 times. ✓ Branch 2 taken 4135321 times. tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<11l> >, std::plus<void>{}, std::negate<void>{}>::find(unsigned int): ✓ Branch 1 taken 8460346 times. ✓ Branch 2 taken 4135321 times. tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<11l> >, std::plus<void>{}, std::negate<void>{}>::find(unsigned int): ✓ Branch 1 taken 8460346 times. ✓ Branch 2 taken 4135321 times. tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, std::plus<void>{}, std::negate<void>{}>::find(unsigned int): ✓ Branch 1 taken 8460346 times. ✓ Branch 2 taken 4135321 times. tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, std::plus<void>{}, std::negate<void>{}>::find(unsigned int): ✓ Branch 1 taken 8460346 times. ✓ Branch 2 taken 4135321 times.	157834527	if (p[x] < 0) return (i32)x;
23		52075357	const auto _ = find((u32)p[x]);
24		52075357	val[x] = op(val[(u32)p[x]], val[x]), p[x] = _;
25		52075357	return _;
26			}
27			ND CEXP u32 size() CNE { return (u32)p.size(); }
28			CEXP u32 size(u32 x) NE { return (u32)-p[(u32)find(x)]; }
29		44515648	CEXP T CR weight(u32 x) NE {
30		44515648	find(x);
31		44515648	return val[x];
32			}
33			// $a_y^{-1}a_x$
34		3695027	CEXP T diff(u32 x, u32 y) NE { return op(inv(weight(y)), weight(x)); }
35		12058964	CEXP bool same(u32 x, u32 y) NE { return find(x) == find(y); }
36		18562797	CEXP bool merge(u32 x, u32 y, T w) NE {
37		18562797	w = op(weight(x), inv(op(weight(y), w)));
38	26/26 tifa_libs::dsu_weighted<long, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, long): ✓ Branch 2 taken 77751 times. ✓ Branch 3 taken 585126 times. tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > >): ✓ Branch 2 taken 157423 times. ✓ Branch 3 taken 1334113 times. tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >): ✓ Branch 2 taken 157423 times. ✓ Branch 3 taken 1334113 times. tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > >): ✓ Branch 2 taken 157423 times. ✓ Branch 3 taken 1334113 times. tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > >): ✓ Branch 2 taken 157423 times. ✓ Branch 3 taken 1334113 times. tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >): ✓ Branch 2 taken 157423 times. ✓ Branch 3 taken 1334113 times. tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >): ✓ Branch 2 taken 157423 times. ✓ Branch 3 taken 1334113 times. tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<11l> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<11l> >): ✓ Branch 2 taken 157633 times. ✓ Branch 3 taken 1334151 times. tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >): ✓ Branch 2 taken 157633 times. ✓ Branch 3 taken 1334151 times. tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<11l> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<11l> >): ✓ Branch 2 taken 157633 times. ✓ Branch 3 taken 1334151 times. tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<11l> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<11l> >): ✓ Branch 2 taken 157633 times. ✓ Branch 3 taken 1334151 times. tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >): ✓ Branch 2 taken 157633 times. ✓ Branch 3 taken 1334151 times. tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >): ✓ Branch 2 taken 157633 times. ✓ Branch 3 taken 1334151 times.	18562797	if ((x = (u32)find(x)) == (y = (u32)find(y))) return w == E;
39	26/26 tifa_libs::dsu_weighted<long, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, long): ✓ Branch 2 taken 119418 times. ✓ Branch 3 taken 465708 times. tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > >): ✓ Branch 2 taken 534506 times. ✓ Branch 3 taken 799607 times. tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >): ✓ Branch 2 taken 534506 times. ✓ Branch 3 taken 799607 times. tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > >): ✓ Branch 2 taken 534506 times. ✓ Branch 3 taken 799607 times. tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > >): ✓ Branch 2 taken 534506 times. ✓ Branch 3 taken 799607 times. tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >): ✓ Branch 2 taken 534506 times. ✓ Branch 3 taken 799607 times. tifa_libs::dsu_weighted<tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, &(op(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&)), &(inv(tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&))>::merge(unsigned int, unsigned int, tifa_libs::matrix<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >): ✓ Branch 2 taken 534506 times. ✓ Branch 3 taken 799607 times. tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<11l> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<11l> >): ✓ Branch 2 taken 535473 times. ✓ Branch 3 taken 798678 times. tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >): ✓ Branch 2 taken 535473 times. ✓ Branch 3 taken 798678 times. tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<11l> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<11l> >): ✓ Branch 2 taken 535473 times. ✓ Branch 3 taken 798678 times. tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<11l> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<11l> >): ✓ Branch 2 taken 535473 times. ✓ Branch 3 taken 798678 times. tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >): ✓ Branch 2 taken 535473 times. ✓ Branch 3 taken 798678 times. tifa_libs::dsu_weighted<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, std::plus<void>{}, std::negate<void>{}>::merge(unsigned int, unsigned int, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >): ✓ Branch 2 taken 535473 times. ✓ Branch 3 taken 798678 times.	16594710	if (p[x] > p[y]) swap(x, y), w = inv(w);
40		16594710	p[x] += p[y], p[y] = (i32)x, val[y] = w;
41		16594710	return true;
42			}
43			};
44
45			} // namespace tifa_libs
46