結果

問題 No.2163 LCA Sum Query
ユーザー 👑 p-adicp-adic
提出日時 2022-12-17 23:20:57
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,261 ms / 6,000 ms
コード長 12,409 bytes
コンパイル時間 4,849 ms
コンパイル使用メモリ 265,332 KB
実行使用メモリ 34,252 KB
最終ジャッジ日時 2024-04-28 14:53:17
合計ジャッジ時間 25,236 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
7,388 KB
testcase_01 AC 4 ms
7,400 KB
testcase_02 AC 5 ms
7,424 KB
testcase_03 AC 5 ms
7,552 KB
testcase_04 AC 5 ms
7,296 KB
testcase_05 AC 6 ms
7,412 KB
testcase_06 AC 4 ms
7,552 KB
testcase_07 AC 5 ms
7,400 KB
testcase_08 AC 5 ms
7,680 KB
testcase_09 AC 5 ms
7,552 KB
testcase_10 AC 5 ms
7,796 KB
testcase_11 AC 5 ms
7,672 KB
testcase_12 AC 400 ms
9,600 KB
testcase_13 AC 561 ms
26,060 KB
testcase_14 AC 411 ms
27,656 KB
testcase_15 AC 155 ms
7,648 KB
testcase_16 AC 331 ms
26,016 KB
testcase_17 AC 361 ms
16,384 KB
testcase_18 AC 251 ms
9,216 KB
testcase_19 AC 184 ms
8,064 KB
testcase_20 AC 40 ms
16,756 KB
testcase_21 AC 182 ms
16,544 KB
testcase_22 AC 859 ms
29,596 KB
testcase_23 AC 761 ms
29,504 KB
testcase_24 AC 825 ms
27,832 KB
testcase_25 AC 934 ms
28,268 KB
testcase_26 AC 1,261 ms
34,252 KB
testcase_27 AC 946 ms
34,248 KB
testcase_28 AC 1,218 ms
33,120 KB
testcase_29 AC 941 ms
33,124 KB
testcase_30 AC 408 ms
24,676 KB
testcase_31 AC 443 ms
24,440 KB
testcase_32 AC 442 ms
23,904 KB
testcase_33 AC 447 ms
23,520 KB
testcase_34 AC 487 ms
25,956 KB
testcase_35 AC 451 ms
25,964 KB
testcase_36 AC 487 ms
24,812 KB
testcase_37 AC 443 ms
24,796 KB
testcase_38 AC 533 ms
25,736 KB
testcase_39 AC 502 ms
25,676 KB
testcase_40 AC 522 ms
24,612 KB
testcase_41 AC 476 ms
24,408 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/x86_64-pc-linux-gnu/bits/c++allocator.h:33,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/allocator.h:46,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/string:41,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/locale_classes.h:40,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/ios_base.h:41,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ios:42,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/istream:38,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/sstream:38,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/complex:45,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ccomplex:39,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:54,
                 from main.cpp:3:
In member function 'void std::__new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = int; _Args = {const int&}; _Tp = std::_List_node<int>]',
    inlined from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = int; _Args = {const int&}; _Tp = std::_List_node<int>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/alloc_traits.h:516:17,
    inlined from 'std::__cxx11::list<_Tp, _Alloc>::_Node* std::__cxx11::list<_Tp, _Alloc>::_M_create_node(_Args&& ...) [with _Args = {const int&}; _Tp = int; _Alloc = std::allocator<int>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_list.h:713:33,
    inlined from 'void std::__cxx11::list<_Tp, _Alloc>::_M_insert(iterator, _Args&& ...) [with _Arg

ソースコード

diff # 

#pragma GCC optimize ( "O3" )
#pragma GCC target ( "avx" )
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) 
#define CEXPR( LL , BOUND , VALUE ) constexpr const LL BOUND = VALUE 
#define CIN( LL , A ) LL A; cin >> A 
#define ASSERT( A , MIN , MAX ) assert( MIN <= A && A <= MAX ) 
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX ) 
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) 
#define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) 
#define FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; VAR -- ) 
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ ) 
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) 
#define QUIT return 0 
#define COUT( ANSWER ) cout << ( ANSWER ) << "\n"; 
#define RETURN( ANSWER ) COUT( ANSWER ); QUIT 

#define first1 first.first
#define second1 first.second
#define third1 second
#define first2 first1
#define second2 second1
#define third2 second.first
#define fourth2 second.second

inline CEXPR( int , bound_N , 50000 );
// lazy_segtree用のデータ１
using S1_12 = pair<ll,ll>;
using S1 = pair<S1_12,ll>;
inline S1 op1( S1 a , S1 b ) { return S1( S1_12( a.first1 + b.first1 , a.second1 + b.second1 ) , a.third1 + b.third1 ); }
inline S1 unit1() { return S1(); }
using F1 = int;
// vが(A,Ax,Ax^2)の形のベクトルの時にfvが(A,A(x+f),A(x+f)^2)=(A,Ax+fA,Ax^2+2fAx+f^2A)となるようなモノイド作用
inline S1 act1( F1 f , S1 v ) { return S1( S1_12( v.first1 , v.second1 + f * v.first1 ) , v.third1 + ( f * 2 ) * v.second1 + ( f * f ) * v.first1 ); }
inline F1 comp1( F1 f1 , F1 f2 ) { return f1 + f2; }
inline F1 id1() { return 0; }

// lazy_segtree用のデータ２
using S2_12 = pair<ll,ll>;
using S2_34 = pair<ll,ll>;
using S2 = pair<S2_12,S2_34>;
inline S2 op2( S2 a , S2 b ) { return S2( S2_12( a.first2 + b.first2 , a.second2 + b.second2 ) , S2_34( a.third2 + b.third2 , a.fourth2 + b.fourth2 ) ); }
inline S2 unit2() { return S2(); }
using F2 = pair<int,int>;
// vが(A,Ax,Ay,Axy)の形のベクトルの時に(f_1,f_2)vが(A,A(x+f_1),A(y+f_2),A(x+f_1)(y+f_2))=(A,Ax+f_1A,Ay+f_2A,Axy+f_1Ay+f_2Ax+f_1f_2A)となるようなモノイド作用
inline S2 act2( F2 f , S2 v ) { return S2( S2_12( v.first2 , v.second2 + f.first * v.first2 ) , S2_34( v.third2 + f.second * v.first2 , v.fourth2 + f.first * v.third2 + f.second * v.second2 + ( f.first * f.second ) * v.first2 ) ); }
inline F2 comp2( F2 f1 , F2 f2 ) { return F2( f1.first + f2.first , f1.second + f2.second ); }
inline F2 id2() { return F2(); }

// lazy_segtree用のデータ３
using S3 = ll;
inline S3 op3( S3 a , S3 b ) { return a + b; }
inline S3 unit3() { return 0; }
using F3 = int;
inline S3 act3( F3 f , S3 v ) { return f + v; }
inline F3 comp3( F3 f1 , F3 f2 ) { return f1 + f2; }
inline F3 id3() { return 0; }

using Interval = pair<int,int>;

#include <atcoder/lazysegtree>
using namespace atcoder;

// 解説におけるf(1,v)の計算
inline ll f1v( int v , int ( &parent )[bound_N+1] , int ( &HL_inv )[bound_N+1] , Interval ( &descendant )[bound_N] , lazy_segtree<S1,op1,unit1,F1,act1,comp1,id1>& v1 , lazy_segtree<S3,op3,unit3,F3,act3,comp3,id3>& v3 )
{
  int& HL_inv_v = HL_inv[v];
  Interval& descendant_v = descendant[HL_inv[v]];
  ll answer = v1.prod( descendant_v.first , descendant_v.second ).third1;
  // 解説におけるXの総和は(Ri,Vi)を(1,v)に置き換えてXを定義し直した時の値であることに注意。
  // 特に(Ri,Vi)=(v,v)!=(1,1)の時のf(v,v)（v!=1）の計算で呼び出されるf(1,1)の計算で参照されるXは問題文中で定義された集合とは別物であり(Ri,Vi)=(1,1)に置き換えて定義し直したものとなる。
  answer -= v3.prod( descendant_v.first , descendant_v.second );
  int& parent_v = parent[v];
  answer += ( v1.get( HL_inv_v ).third1 / ( v - parent_v ) ) * parent_v;
  answer /= 2;
  return answer;
}

// 解説におけるf(v,v)の計算
inline ll fvv( int v , int ( &parent )[bound_N+1] , int ( &HL_inv )[bound_N+1] , Interval ( &descendant )[bound_N] , list<Interval> ( &path )[bound_N] , lazy_segtree<S1,op1,unit1,F1,act1,comp1,id1>& v1 , lazy_segtree<S2,op2,unit2,F2,act2,comp2,id2>& v2 , lazy_segtree<S3,op3,unit3,F3,act3,comp3,id3>& v3 )
{
  ll answer = f1v( 1 , parent , HL_inv , descendant , v1 , v3 );
  list<Interval>& path_v = path[HL_inv[v]];
  FOR_ITR( path_v , itr_v , end_v ){
    // |S|-c(root,root) = 0であるので本来不要なrootの寄与は自動的に消える
    answer += v2.prod( itr_v->first , itr_v->second ).fourth2;
  }
  return answer;
}

int main()
{
  UNTIE;
  CIN_ASSERT( N , 1 , bound_N );
  CEXPR( int , bound_Q , 100000 );
  CIN_ASSERT( Q , 1 , bound_Q );
  // 一旦子と親を全て同じ配列に格納
  list<int> children[bound_N+1] = {};
  FOR( i , 1 , N ){
    CIN_ASSERT( Ai , 1 , N );
    CIN_ASSERT( Bi , 1 , N );
    assert( Ai != Bi );
    children[Ai].push_back( Bi );
    children[Bi].push_back( Ai );
  }
  // 子と親の決定
  int parent[bound_N+1];
  // 解説では各vに対するf(1,v)の表示の第1項の計算畤に各xに対するx-(xの親)を参照しておりx=1の時に未定義参照となるが、
  // 等式自体は(xの親)を好きな定数に置き換えても成り立つのでここでは(1の親)を定数で置き換える。
  // f(1,v)の表示の第3項を遅延セグメント木から復元する際にv-(vの親)で割る必要があるので、(1の親)を置き換える定数は1以外にする必要がある。
  parent[1] = 0;
  list<int> layer[bound_N] = {};
  int children_query[bound_N];
  children_query[0] = 1;
  int start_children_query = 0;
  int size_children_query = 1;
  int size_children_query_copy = size_children_query;
  int depth = 0;
  while( start_children_query < size_children_query ){
    list<int>& layer_curr = layer[depth];
    FOR( i , start_children_query , size_children_query ){
      int& children_query_i = children_query[i];
      layer_curr.push_back( children_query_i );
      list<int>& children_i = children[children_query_i];
      FOR_ITR( children_i , itr_i , end_i ){
	int& j = *itr_i;
	parent[j] = children_query_i;
	list<int>& children_ij = children[j];
	FOR_ITR( children_ij , itr_ij , end_ij ){
	  if( children_query_i == *itr_ij ){
	    children_ij.erase( itr_ij );
	    break;
	  }
	}
	children_query[size_children_query_copy++] = j;
      }
    }
    depth++;
    start_children_query = size_children_query;
    size_children_query = size_children_query_copy;
  }
  // HL分解のための重さ計算
  int weight[bound_N + 1];
  FOREQINV( d , depth - 1 , 0 ){
    list<int>& layer_curr = layer[d];
    FOR_ITR( layer_curr , itr_d , end_d ){
      int& i = *itr_d;
      list<int>& children_curr = children[i];
      int& weight_i = weight[i];
      weight_i = 1;
      FOR_ITR( children_curr , itr_i , end_i ){
	weight_i += weight[*itr_i];
      }
    }
  }
  // HL分解のためのheight計算
  int children_H_i;
  int weight_max;
  FOREQ( i , 1 , N ){
    list<int>& children_i = children[i];
    weight_max = -1;
    FOR_ITR( children_i , itr , end ){
      int& j_curr = *itr;
      int& weight_j_curr = weight[j_curr];
      if( weight_max < weight_j_curr ){
	weight_max = weight_j_curr;
	children_H_i = j_curr;
      }
    }
    FOR_ITR( children_i , itr , end ){
      if( children_H_i == *itr ){
	children_i.erase( itr );
	children_i.push_front( children_H_i );
	break;
      }
    }
  }
  // HL分解
  // 添え字は0始まり、根に小さい番号づけ。
  // この向きでないとH側のpathが区間になるだけで部分木が１つの区間にならず区間族になることに注意。
  int HL[bound_N];
  int HL_inv[bound_N+1];
  list<int> root{ { 1 } };
  list<list<int>::iterator> children_itr_stack{};
  children_itr_stack.push_back( root.begin() );
  list<list<int>::iterator> children_end_stack{};
  children_end_stack.push_back( root.end() );
  int length = 0;
  while( ! children_itr_stack.empty() ){
    list<int>::iterator& itr_curr = children_itr_stack.back();
    list<int>::iterator& end_curr = children_end_stack.back();
    if( itr_curr == end_curr ){
      children_itr_stack.pop_back();
      children_end_stack.pop_back();
    } else {
      int& i_curr = *itr_curr;
      HL_inv[i_curr] = length;
      HL[length++] = i_curr;
      list<int>& children_curr = children[i_curr];
      children_itr_stack.push_back( children_curr.begin() );
      children_end_stack.push_back( children_curr.end() );
      itr_curr++;
    }
  }
  // 1からのパスのなすHL上の半開区間[first,second)の計算（ここが各ノードでlogオーダーになることがHL分解特有の事情）
  list<Interval> path[bound_N];
  path[0] = list<Interval>( { Interval( 0 , 1 ) } );
  FOR( d , 1 , depth ){
    list<int>& layer_curr = layer[d];
    FOR_ITR( layer_curr , itr_d , end_d ){
      int& i = *itr_d;
      int& parent_i = parent[i];
      int& HL_inv_parent_i = HL_inv[parent_i];
      int& HL_inv_i = HL_inv[i];
      list<Interval>& path_parent_i = path[HL_inv_parent_i];
      list<Interval>& path_i = path[HL_inv_i];
      path_i = path_parent_i;
      if( children[parent_i].front() == i ){
	path_i.back().second = HL_inv_i + 1;
      } else {
	path_i.push_back( Interval( HL_inv_i , HL_inv_i + 1 ) );
      }
    }
  }
  // ノードの子孫のなすHL上の半開区間[first,second)の計算
  Interval descendant[bound_N];
  FOREQINV( d , depth - 1 , 0 ){
    list<int>& layer_curr = layer[d];
    FOR_ITR( layer_curr , itr_d , end_d ){
      int& i = *itr_d;
      list<int>& children_curr = children[i];
      int& HL_inv_i = HL_inv[i];
      descendant[HL_inv_i] = Interval( HL_inv_i , children_curr.empty() ? HL_inv_i + 1 : descendant[HL_inv[children_curr.back()]].second );
    }
  }
  // 解説における(x-(xの親),(x-(xの親))c(1,x),(x-(xの親))c(1,x)^2)の管理
  lazy_segtree<S1,op1,unit1,F1,act1,comp1,id1> v1{ N };
  FOR( i , 0 , N ){
    int& HL_i = HL[i];
    v1.set( i , S1( S1_12( HL_i - parent[HL_i] , 0 ) , 0 ) );
  }
  // 解説における(x-(xの親),(x-(xの親))c(1,x),(x-(xの親))(|S|-c(1,x)),(x-(xの親))c(1,x)(|S|-c(1,x)))の管理
  lazy_segtree<S2,op2,unit2,F2,act2,comp2,id2> v2{ N };
  FOR( i , 0 , N ){
    int& HL_i = HL[i];
    v2.set( i , S2( S2_12( HL_i - parent[HL_i] , 0 ) , S2_34( 0 , 0 ) ) );
  }
  // Xの総和を計算するための(x in S ? x : 0)の管理
  lazy_segtree<S3,op3,unit3,F3,act3,comp3,id3> v3{ N };
  set<int> S{};
  int sign , x , HL_inv_x;
  bool belong;
  // クエリ処理
  REPEAT( Q ){
    CIN_ASSERT( Ui , 1 , N );
    CIN_ASSERT( Ri , 1 , N );
    CIN_ASSERT( Vi , 1 , N );
    if( S.count( Ui ) == 0 ){
      sign = 1;
      S.insert( Ui );
    } else {
      sign = -1;
      S.erase( Ui );
    }
    int& HL_inv_Ui = HL_inv[Ui];
    v3.apply( HL_inv_Ui , sign * Ui );
    v2.apply( 0 , N , F2( 0 , sign ) );
    list<Interval>& path_Ui = path[HL_inv[Ui]];
    FOR_ITR( path_Ui , itr_i , end_i ){
      Interval& path_Uij = *itr_i;
      v1.apply( path_Uij.first , path_Uij.second , sign );
      v2.apply( path_Uij.first , path_Uij.second , F2( sign , -sign ) );
    }
    int& HL_inv_Vi = HL_inv[Vi];
    if( Ri == Vi ){
      COUT( fvv( Vi , parent , HL_inv , descendant , path , v1 , v2 , v3 ) );
    } else {
      int& HL_inv_Ri = HL_inv[Ri];
      belong = false;
      list<Interval>& path_Ri = path[HL_inv_Ri];
      FOR_ITR( path_Ri , itr_Ri , end_Ri ){
	Interval& path_Rij = *itr_Ri;
	if( path_Rij.first <= HL_inv_Vi && HL_inv_Vi < path_Rij.second ){
	  belong = true;
	  if( HL_inv_Vi + 1 == path_Rij.second ){
	    itr_Ri++;
	    HL_inv_x = itr_Ri->first;
	  } else {
	    HL_inv_x = HL_inv_Vi + 1;
	  }
	  x = HL[HL_inv_x];
	  COUT( fvv( Vi , parent , HL_inv , descendant , path , v1 , v2 , v3 ) - f1v( x , parent , HL_inv , descendant , v1 , v3 ) - ( v2.get( HL_inv_x ).fourth2 / ( x - Vi ) ) * Vi );
	  break;
	}
      }
      if( ! belong ){
	COUT( f1v( Vi , parent , HL_inv , descendant , v1 , v3 ));
      }
    }
  }
  QUIT;
}
0