【HDU】5436 Transmigration tree【树链剖分+dp+rmq】

本文主要是介绍【HDU】5436 Transmigration tree【树链剖分+dp+rmq】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：【HDU】5436 Transmigration tree

#pragma comment(linker, "/STACK:16777216")
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std ;typedef long long LL ;#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 50005 ;vector < int > G[MAXN] ;
int dep[MAXN] ;
int siz[MAXN] ;
int son[MAXN] ;
int pre[MAXN] ;
int pos[MAXN] ;
int top[MAXN] ;
int tree_idx ;int maxv[MAXN][18] ;
int dp[MAXN][2] ;
int qp[MAXN][2] ;
pair < int , int > up[MAXN] ;
pair < int , int > L[MAXN] ;
pair < int , int > R[MAXN] ;
int w[MAXN] ;
int sum[MAXN] ;
int n , q ;void dfs ( int u ) {son[u] = 0 ;siz[u] = 1 ;for ( int i = 0 ; i < G[u].size () ; ++ i ) {int v = G[u][i] ;pre[v] = u ;dep[v] = dep[u] + 1 ;dfs ( v ) ;siz[u] += siz[v] ;if ( siz[v] > siz[son[u]] ) son[u] = v ;}
}void rebuild ( int u , int top_element ) {pos[u] = ++ tree_idx ;top[u] = top_element ;if ( son[u] ) rebuild ( son[u] , top_element ) ;for ( int i = 0 ; i < G[u].size () ; ++ i ) {int v = G[u][i] ;if ( v != pre[u] && v != son[u] ) rebuild ( v , v ) ;}
}void dfs2 ( int u ) {qp[u][0] = 1e9 ;qp[u][1] = 0 ;int leaf = 1 ;for ( int i = 0 ; i < G[u].size () ; ++ i ) {int v = G[u][i] ;dp[v][0] = dp[u][0] + w[pos[v]] ;dp[v][1] = max ( dp[u][1] , w[pos[v]] ) ;dfs2 ( v ) ;leaf = 0 ;if ( qp[u][0] > qp[v][0] ) {qp[u][0] = qp[v][0] ;qp[u][1] = qp[v][1] ;} else if ( qp[u][0] == qp[v][0] ) {qp[u][1] = max ( qp[u][1] , qp[v][1] ) ;}}if ( leaf ) qp[u][0] = w[pos[u]] ;else qp[u][0] += w[pos[u]] ;qp[u][1] = max ( qp[u][1] , w[pos[u]] ) ;
}void dfs3 ( int u ) {int n = G[u].size () ;if ( n == 0 ) return ;L[0] = make_pair ( -1e9 , 0 ) ;R[n - 1] = make_pair ( -1e9 , 0 ) ;for ( int i = 1 ; i < n ; ++ i ) {int v = G[u][i - 1] ;L[i] = max ( L[i - 1] , make_pair ( -qp[v][0] , qp[v][1] ) ) ;}for ( int i = n - 2 ; i >= 0 ; -- i ) {int v = G[u][i + 1] ;R[i] = max ( R[i + 1] , make_pair ( -qp[v][0] , qp[v][1] ) ) ;}for ( int i = 0 ; i < n ; ++ i ) {int v = G[u][i] ;pair < int , int > t = max ( L[i] , R[i] ) ;up[v] = max ( up[u] , make_pair ( t.first - w[pos[u]] , max ( t.second , w[pos[u]] ) ) ) ;up[v].first -= w[pos[v]] ;up[v].second = max ( up[v].second , w[pos[v]] ) ;}for ( int i = 0 ; i < n ; ++ i ) {int v = G[u][i] ;dfs3 ( v ) ;}
}void init_RMQ ( int n ) {for ( int i = 1 ; i <= n ; ++ i ) maxv[i][0] = w[i] ;for ( int j = 1 ; ( 1 << j ) < n ; ++ j ) {for ( int i = 1 ; i + ( 1 << j ) - 1 <= n ; ++ i ) {maxv[i][j] = max ( maxv[i][j - 1] , maxv[i + ( 1 << ( j - 1 ) )][j - 1] ) ;}}
}int rmq ( int L , int R , int k = 0 ) {while ( ( 1 << ( k + 1 ) ) <= R - L + 1 ) ++ k ;return max ( maxv[L][k] , maxv[R - ( 1 << k ) + 1][k] ) ;
}pair < int , int > getval ( int x , int y ) {int ans1 = 0 , ans2 = 0 ;while ( top[x] != top[y] ) {if ( dep[top[x]] < dep[top[y]] ) swap ( x , y ) ;ans1 += sum[pos[x]] - sum[pos[top[x]] - 1] ;ans2 = max ( ans2 , rmq ( pos[top[x]] , pos[x] ) ) ;x = pre[top[x]] ;}if ( dep[x] > dep[y] ) swap ( x , y ) ;ans1 += sum[pos[y]] - sum[pos[x] - 1] ;ans2 = max ( ans2 , rmq ( pos[x] , pos[y] ) ) ;return make_pair ( -ans1 , ans2 ) ;
}void solve () {int u , v ;tree_idx = 0 ;scanf ( "%d%d" , &n , &q ) ;for ( int i = 1 ; i <= n ; ++ i ) {G[i].clear () ;}for ( int i = 2 ; i <= n ; ++ i ) {scanf ( "%d" , &u ) ;G[u].push_back ( i ) ;}dfs ( 1 ) ;rebuild ( 1 , 1 ) ;for ( int i = 1 ; i <= n ; ++ i ) {scanf ( "%d" , &w[pos[i]] ) ;}dp[1][0] = w[pos[1]] ;dp[1][1] = w[pos[1]] ;up[1] = make_pair ( -1e9 , 0 ) ;for ( int i = 2 ; i <= n ; ++ i ) {dp[i][0] = dp[i][1] = 0 ;}dfs2 ( 1 ) ;dfs3 ( 1 ) ;for ( int i = 1 ; i <= n ; ++ i ) {pair < int , int > t = make_pair ( -qp[i][0] , qp[i][1] ) ;if ( t < up[i] ) t = up[i] ;qp[i][0] = -t.first ;qp[i][1] = t.second ;}init_RMQ ( n ) ;for ( int i = 1 ; i <= n ; ++ i ) {sum[i] = sum[i - 1] + w[i] ;}for ( int i = 0 ; i < q ; ++ i ) {scanf ( "%d%d" , &u , &v ) ;pair < int , int > t1 = getval ( u , v ) ;pair < int , int > t2 = make_pair ( - dp[u][0] - qp[v][0] , max ( dp[u][1] , qp[v][1] ) ) ;pair < int , int > t3 = make_pair ( - dp[v][0] - qp[u][0] , max ( dp[v][1] , qp[u][1] ) ) ;pair < int , int > t4 = make_pair ( - qp[v][0] - qp[u][0] - w[pos[1]] , max ( w[pos[1]] , max ( qp[v][1] , qp[u][1] ) ) ) ;if ( t2 > t1 ) t1 = t2 ;if ( t3 > t1 ) t1 = t3 ;if ( t4 > t1 ) t1 = t4 ;printf ( "%d %d\n" , -t1.first , t1.second ) ;}
}int main () {int T ;scanf ( "%d" , &T ) ;for ( int i = 1 ; i <= T ; ++ i ) {solve () ;}return 0 ;
}

这篇关于【HDU】5436 Transmigration tree【树链剖分+dp+rmq】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---