結果
| 問題 | No.2163 LCA Sum Query |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2022-12-17 10:36:48 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 18,676 bytes |
| コンパイル時間 | 4,466 ms |
| コンパイル使用メモリ | 266,424 KB |
| 実行使用メモリ | 51,368 KB |
| 最終ジャッジ日時 | 2024-11-16 19:14:43 |
| 合計ジャッジ時間 | 149,209 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 5 ms
34,524 KB |
| testcase_01 | AC | 5 ms
13,828 KB |
| testcase_02 | AC | 10 ms
34,036 KB |
| testcase_03 | AC | 10 ms
34,700 KB |
| testcase_04 | AC | 10 ms
39,168 KB |
| testcase_05 | AC | 9 ms
31,088 KB |
| testcase_06 | AC | 6 ms
30,952 KB |
| testcase_07 | AC | 6 ms
30,732 KB |
| testcase_08 | AC | 7 ms
30,840 KB |
| testcase_09 | AC | 10 ms
31,140 KB |
| testcase_10 | AC | 14 ms
31,012 KB |
| testcase_11 | AC | 8 ms
12,672 KB |
| testcase_12 | AC | 1,973 ms
32,832 KB |
| testcase_13 | AC | 5,242 ms
49,260 KB |
| testcase_14 | AC | 3,082 ms
51,368 KB |
| testcase_15 | AC | 689 ms
7,424 KB |
| testcase_16 | AC | 3,225 ms
25,948 KB |
| testcase_17 | AC | 2,783 ms
16,068 KB |
| testcase_18 | AC | 1,629 ms
8,960 KB |
| testcase_19 | AC | 1,058 ms
7,652 KB |
| testcase_20 | AC | 456 ms
16,456 KB |
| testcase_21 | AC | 1,839 ms
16,236 KB |
| testcase_22 | TLE | - |
| testcase_23 | TLE | - |
| testcase_24 | TLE | - |
| testcase_25 | TLE | - |
| testcase_26 | TLE | - |
| testcase_27 | AC | 2,918 ms
34,052 KB |
| testcase_28 | TLE | - |
| testcase_29 | AC | 2,779 ms
32,932 KB |
| testcase_30 | TLE | - |
| testcase_31 | TLE | - |
| testcase_32 | TLE | - |
| testcase_33 | TLE | - |
| testcase_34 | TLE | - |
| testcase_35 | AC | 941 ms
25,764 KB |
| testcase_36 | TLE | - |
| testcase_37 | AC | 796 ms
24,612 KB |
| testcase_38 | TLE | - |
| testcase_39 | TLE | - |
| testcase_40 | TLE | - |
| testcase_41 | TLE | - |
コンパイルメッセージ
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:4:
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
ソースコード
// #define _GLIBCXX_DEBUG
#pragma GCC optimize ( "O3" )
#pragma GCC target ( "avx" )
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
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 GETLINE( A ) string A; getline( cin , A )
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR )
#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 COUT( ANSWER ) cout << ( ANSWER ) << endl;
#define RETURN( ANSWER ) COUT( ANSWER ); QUIT
#define DOUBLE( PRECISION , ANSWER ) cout << fixed << setprecision( PRECISION ) << ( ANSWER ) << "\n"; QUIT
#define POWER( ANSWER , ARGUMENT , EXPONENT ) \
TYPE_OF( ARGUMENT ) ANSWER{ 1 }; \
{ \
TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT ); \
TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \
while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \
if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \
ANSWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \
} \
ARGUMENT_FOR_SQUARE_FOR_POWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \
EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \
} \
} \
#define POWER_MOD( ANSWER , ARGUMENT , EXPONENT , MODULO ) \
TYPE_OF( ARGUMENT ) ANSWER{ 1 }; \
{ \
TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( MODULO + ( ARGUMENT ) % MODULO ) % MODULO; \
TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \
while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \
if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \
ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \
} \
ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \
EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \
} \
} \
#define FACTORIAL_MOD( ANSWER , ANSWER_INV , MAX_I , LENGTH , MODULO ) \
ll ANSWER[LENGTH]; \
ll ANSWER_INV[LENGTH]; \
{ \
ll VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \
ANSWER[0] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL; \
FOREQ( i , 1 , MAX_I ){ \
ANSWER[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= i ) %= MODULO; \
} \
POWER_MOD( FACTORIAL_MAX_INV , ANSWER[MAX_I] , MODULO - 2 , MODULO ); \
ANSWER_INV[MAX_I] = FACTORIAL_MAX_INV; \
FOREQINV( i , MAX_I - 1 , 0 ){ \
ANSWER_INV[i] = ( FACTORIAL_MAX_INV *= i + 1 ) %= MODULO; \
} \
} \
\
// 通常の二分探索
#define BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
ll ANSWER = MAXIMUM; \
{ \
ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \
ll VARIABLE_FOR_BINARY_SEARCH_U = ANSWER; \
ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \
} else { \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
} \
while( VARIABLE_FOR_BINARY_SEARCH_L != ANSWER ){ \
VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \
break; \
} else { \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \
} else { \
VARIABLE_FOR_BINARY_SEARCH_U = ANSWER; \
} \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
} \
} \
} \
\
// 二進法の二分探索
#define BS2( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
ll ANSWER = MINIMUM; \
{ \
ll VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 = 1; \
ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( MAXIMUM ) - ANSWER; \
while( VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 <= VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ){ \
VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 *= 2; \
} \
VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 /= 2; \
ll VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER; \
while( VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 != 0 ){ \
ANSWER = VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 + VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2; \
VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \
VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER; \
break; \
} else if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){ \
VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER; \
} \
VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 /= 2; \
} \
ANSWER = VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2; \
} \
\
template <typename T> inline T Absolute( const T& a ){ return a > 0 ? a : - a; }
template <typename T> inline T Residue( const T& a , const T& p ){ return a >= 0 ? a % p : p - ( - a - 1 ) % p - 1; }
#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;
// Xの総和を計算するための、部分木におけるS内の総和の計算
ll sum_v3( int v , list<int> ( &children )[bound_N+1] , int ( &HL_inv )[bound_N+1] , int ( &leftmost_descendant )[bound_N] , lazy_segtree<S3,op3,unit3,F3,act3,comp3,id3>& v3 )
{
int& HL_inv_v = HL_inv[v];
ll answer = v3.prod( leftmost_descendant[HL_inv_v] , HL_inv_v + 1 );
list<int>* p_children_v = &( children[v] );
while( ! p_children_v->empty() ){
auto itr_v = p_children_v->begin() , end_v = p_children_v->end();
v = *itr_v;
p_children_v = &( children[v] );
while( ++itr_v != end_v ){
answer += sum_v3( *itr_v , children , HL_inv , leftmost_descendant , v3 );
}
}
return answer;
}
// 解説におけるf(1,v)の表示の第1項の計算
ll sum_v1( int v , list<int> ( &children )[bound_N+1], int ( &HL_inv )[bound_N+1] , int ( &leftmost_descendant )[bound_N] , lazy_segtree<S1,op1,unit1,F1,act1,comp1,id1>& v1 )
{
int& HL_inv_v = HL_inv[v];
// 解説ではvの親に言及しているため暗にv != 1を課しているが、ここではrootの親を便宜上0とすることで場合分けを回避
ll answer = v1.prod( leftmost_descendant[HL_inv_v] , HL_inv_v + 1 ).third1;
list<int>* p_children_v = &( children[v] );
while( ! p_children_v->empty() ){
auto itr_v = p_children_v->begin() , end_v = p_children_v->end();
v = *itr_v;
p_children_v = &( children[v] );
while( ++itr_v != end_v ){
answer += sum_v1( *itr_v , children , HL_inv , leftmost_descendant , v1 );
}
}
return answer;
}
// 解説におけるf(1,v)の計算
inline ll f1v( int v , list<int> ( &children )[bound_N+1] , int ( &parent )[bound_N+1] , int ( &HL_inv )[bound_N+1] , int ( &leftmost_descendant )[bound_N] , lazy_segtree<S1,op1,unit1,F1,act1,comp1,id1>& v1 , lazy_segtree<S3,op3,unit3,F3,act3,comp3,id3>& v3 )
{
list<int>& children_v = children[v];
int& HL_inv_v = HL_inv[v];
ll answer = sum_v1( v , children , HL_inv , leftmost_descendant , v1 );
// 解説における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 -= sum_v3( v , children , HL_inv , leftmost_descendant , v3 );
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 , list<int> ( &children )[bound_N+1] , int ( &parent )[bound_N+1] , int ( &HL_inv )[bound_N+1] , int ( &leftmost_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 , children , parent , HL_inv , leftmost_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 + 1 ).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];
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始まり、葉に小さい番号づけ）
int HL[bound_N];
int HL_inv[bound_N+1];
list<int> vertex_stack{};
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;
list<int>& children_curr = children[i_curr];
auto itr_new = children_curr.begin() , end_new = children_curr.end();
if( itr_new == end_new ){
HL_inv[i_curr] = length;
HL[length++] = i_curr;
FOR_ITR( vertex_stack , itr_v , end_v ){
int& i_prev = *itr_v;
HL_inv[i_prev] = length;
HL[length++] = i_prev;
}
vertex_stack.clear();
} else {
vertex_stack.push_front( i_curr );
children_itr_stack.push_back( itr_new );
children_end_stack.push_back( end_new );
}
itr_curr++;
}
}
// 1からのパス計算（ここが各ノードでlogオーダーになることがHL分解特有の事情）
int& HL_inv_root = HL_inv[1];
list<Interval> path[bound_N];
path[HL_inv_root] = list<Interval>( { Interval( HL_inv_root , HL_inv_root ) } );
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().first = HL_inv_i;
} else {
path_i.push_back( Interval( HL_inv_i , HL_inv_i ) );
}
}
}
// ノードの子孫のなすHL上の区間の左端の決定
int leftmost_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];
leftmost_descendant[HL_inv_i] = children_curr.empty() ? HL_inv_i : leftmost_descendant[HL_inv[children_curr.front()]];
}
}
// 解説における(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 , HL_inv_Ui + 1, 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 + 1 , sign );
v2.apply( path_Uij.first , path_Uij.second + 1 , F2( sign , -sign ) );
}
int& HL_inv_Vi = HL_inv[Vi];
if( Ri == Vi ){
COUT( fvv( Vi , children , parent , HL_inv , leftmost_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( path_Rij.first == HL_inv_Vi ){
itr_Ri++;
HL_inv_x = itr_Ri->second;
} else {
HL_inv_x = HL_inv_Vi - 1;
}
x = HL[HL_inv_x];
COUT( fvv( Vi , children , parent , HL_inv , leftmost_descendant , path , v1 , v2 , v3 ) - f1v( x , children , parent , HL_inv , leftmost_descendant , v1 , v3 ) - ( v2.prod( HL_inv_x , HL_inv_x + 1 ).fourth2 / ( x - Vi ) ) * Vi );
break;
}
}
if( ! belong ){
COUT( f1v( Vi , children , parent , HL_inv , leftmost_descendant , v1 , v3 ));
}
}
}
QUIT;
}