给出一个N个点的无根树,节点有黑或白两种颜色,初始时节点全是黑色,现在有以下两个操作:
1. G :询问树上最远的黑色点对的距离,如果只有一个黑点则输出0,没有黑点则输出-1
2. C x:将点x的颜色取反
输入格式:
第一行一个整数N表示节点数
接下来N-1行,每行两个整数u , v,表示有一条边连接了u和v
接下来一行一个整数Q,表示操作个数
再接下来Q行,每行一个操作,格式如题
输出格式:
对于每个询问操作,输出答案
第一道点分树的题=w=
me记得很久很久以前me写过这道题的括号序做法,现在估计也忘光光了hhhhh
因为me也是看的题解,所以就直接说做法好了…
首先像跑普通点分治那样,把每一层的重心找出来,然后当前层的重心连接上一层的重心,以此可以构建出一个「点分树」。构建这棵树肯定是有好处的(废话),因为重心的性质,与重心相连的子树大小都不超过总节点数的一半,因此点分树最多只会有
考虑如何维护信息,在每个节点都开两个大根堆,1号堆里存的是「当前重心的辖区内,所有节点到上一层重心(点分树父亲)的距离」,2号堆里存的是「所有子重心(点分树儿子)的1号堆的堆顶」。很明显,答案就是所有2号堆中「最大值+次大值」最大的那一个(注意要考虑单链的情况),这个可以再开一个堆来维护。
剩下的就是修改操作啦,加油思考吧 =w=
(Tips:因为更改一个点的颜色最多只会影响到 它的点分树祖先,是log级别的,因此可以去修改这些信息来维护答案。具体的,把原来的影响减掉,现在的影响加上即可。还有还有,所有的黑点都需要在2号堆里额外存一个0,这样就可以把单链的情况也考虑到。求两点距离可以用dep[u]+dep[v]-2*dep[LCA])
真 大常数,居然跑了17秒= =???
懒得优化了,丑就丑叭…
/************************************************************** Problem: 1095 User: Izumihanako Language: C++ Result: Accepted Time:17484 ms Memory:140784 kb ****************************************************************/ #include#include #include #include #define ON true #define OFF false using namespace std ; bool status[100005] ; int N , Q , head[100005] , fa[100005] , tp , lighton , root ; struct Heap{ priority_queue heap , del ; void insert( const int &x ){ heap.push( x ) ; } void Delete( const int &x ){ del.push( x ) ; } void update(){ while( !del.empty() && heap.top() == del.top() ) heap.pop() , del.pop() ; } int size() { update() ; return heap.size() - del.size() ; } bool empty(){ update() ; return heap.empty() ; } void pop() { update() ; heap.pop() ; } int top() { update() ; return heap.top() ; } int second_top(){ int tmp = top() ; pop() ; int rt = top() ; insert( tmp ) ; return rt ; } }Hson[100005] , Htop[100005] , ans ; struct Path{ int pre , to ; }p[200005] ; void In( int t1 , int t2 ){ p[++tp].pre = head[t1] ; p[ head[t1] = tp ].to = t2 ; } int ST[18][200005] , logg[200005] ; int dep[100005] , in[100005] , dfs_c ; void dfs_RMQ( int u , int f ){ ST[0][ in[u] = ++dfs_c ] = dep[u] ; for( int i = head[u] ; i ; i = p[i].pre ){ int v = p[i].to ; if( v == f ) continue ; dep[v] = dep[u] + 1 ; dfs_RMQ( v , u ) ; ST[0][ ++dfs_c ] = dep[u] ; } } void init_ST(){ logg[1] = 0 ; logg[2] = 1 ; logg[3] = 1 ; for( int i = 4 ; i <= dfs_c ; i ++ ) logg[i] = logg[i>>1] + 1 ; for( int i = 1 ; i <= 17 ; i ++ ) for( int j = 1 ; j <= dfs_c ; j ++ ) ST[i][j] = min( ST[i-1][j] , ST[i-1][j+(1<<(i-1))] ) ; } int Query( int lf , int rg ){ if( lf > rg ) swap( lf , rg ) ; int x = logg[ rg - lf + 1 ] ; return min( ST[x][lf] , ST[x][rg-(1< in[v] ) swap( u , v ) ; return dep[u] + dep[v] - 2 * Query( in[u] , in[v] ) ; } bool vis[100005] ; int Gr , siz[100005] , maxs[100005] , totsiz ; void getG( int u , int f ){ siz[u] = 1 , maxs[u] = 0 ; for( int i = head[u] ; i ; i = p[i].pre ){ int v = p[i].to ; if( v == f || vis[v] ) continue ; getG( v , u ) ; siz[u] += siz[v] ; maxs[u] = max( maxs[u] , siz[v] ) ; } maxs[u] = max( maxs[u] , totsiz - siz[u] ) ; if( maxs[Gr] > maxs[u] ) Gr = u ; } void div_tree( int u ){ vis[u] = true ; for( int i = head[u] ; i ; i = p[i].pre ){ int v = p[i].to ; if( vis[v] ) continue ; Gr = 0 , totsiz = siz[v] ; getG( v , u ) ; fa[Gr] = u ; div_tree( Gr ) ; } } void Del_ans( int u ){ if( Htop[u].size() >= 2 ) ans.Delete( Htop[u].top() + Htop[u].second_top() ) ; } void Ins_ans( int u ){ if( Htop[u].size() >= 2 ) ans.insert( Htop[u].top() + Htop[u].second_top() ) ; } void turn_on( int u ){ int tmp = u ; Del_ans( u ) ; Htop[u].Delete( 0 ) ; Ins_ans( u ) ; status[u] = ON , lighton ++ ; while( fa[tmp] ){ Del_ans( fa[tmp] ) ; Htop[ fa[tmp] ].Delete( Hson[tmp].top() ) ; Hson[tmp].Delete( dis( fa[tmp] , u ) ) ; if( !Hson[tmp].empty() ) Htop[ fa[tmp] ].insert( Hson[tmp].top() ) ; Ins_ans( fa[tmp] ) ; tmp = fa[tmp] ; } } void turn_off( int u ){ int tmp = u ; Del_ans( u ) ; Htop[u].insert( 0 ) ; Ins_ans( u ) ; status[u] = OFF , lighton -- ; while( fa[tmp] ){ Del_ans( fa[tmp] ) ; if( !Hson[tmp].empty() ) Htop[ fa[tmp] ].Delete( Hson[tmp].top() ) ; Hson[tmp].insert( dis( fa[tmp] , u ) ) ; Htop[ fa[tmp] ].insert( Hson[tmp].top() ) ; Ins_ans( fa[tmp] ) ; tmp = fa[tmp] ; } } void init(){ dfs_RMQ( 1 , 1 ) ; init_ST() ; totsiz = N , maxs[0] = 0x3f3f3f3f ; getG( 1 , 1 ) ; root = Gr ; div_tree( Gr ) ; for( int i = 1 ; i <= N ; i ++ ) status[i] = ON ; for( int i = 1 ; i <= N ; i ++ ) turn_off( i ) ; } void solve(){ scanf( "%d" , &Q ) ; char opt[5] ; for( int i = 1 , x ; i <= Q ; i ++ ){ scanf( "%s" , opt ) ; if( opt[0] == 'G' ){ if( lighton == N - 1 ) puts( "0" ) ; else if( lighton == N ) puts( "-1" ) ; else printf( "%d\n" , ans.top() ) ; } else{ scanf( "%d" , &x ) ; if( status[x] == ON ) turn_off( x ) ; else turn_on( x ) ; } } } int main(){ scanf( "%d" , &N ) ; lighton = N ; for( int i = 1 , u , v ; i < N ; i ++ ){ scanf( "%d%d" , &u , &v ) ; In( u , v ) ; In( v , u ) ; } init() ; solve() ; }