[PKU/POJ][3162][Walking Race][线段树＋树形DP]

1.给你一棵边带权的树，求出树中每一个点到其它点的最大距离。

2.在一个整数序列中找一个最大的连续序列，使得该序列中最大数和最小数之差不超过 m 。

问题 1 可用树形 DP 解决。对树进行 DFS，DFS 过程中，对根 R，记录他的孩子结点到他是最大距离和次大距离以及相应的结点。然后用一次 BFS 更新。

问题 2 用两个指针 head, tail分别指向连续序列的首尾，如果区间 [head,tail] 满足条件，则 tail++,更新值最大最小值，不满足条件则 head++, 用线段树更新最大最小值。

 

注意图不能用 STL 的 vector 和 pair 保存，这样会 TLE。

 

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int const N= 1000010, inf= 0x7fffffff;
int dp[N][2], pos[N][2], flag[N], que[N];
int n, m, cnt;

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

struct Edge{
	int adj, wt;
	Edge* next;
}EG[N<<1];

Edge* mat[N];

struct TB{
	int Min, Max;
}tb[N<<2];

inline void add( int u, int v, int d ){
	++cnt;
	EG[cnt].adj= v; EG[cnt].wt= d; 
	EG[cnt].next= mat[u]; mat[u]= EG+ cnt;
	
	cnt++;
	EG[cnt].adj= u; EG[cnt].wt= d;
	EG[cnt].next= mat[v]; mat[v]= EG+ cnt;
}

int dfs( int u ){
	dp[u][0]= 0; dp[u][1]= 0; flag[u]= 1;
	
	for( Edge* p= mat[u]; p; p= p->next )
	if( !flag[p->adj] ){
		int v= p->adj, w= p->wt;
		
		int tmp= w+ dfs( v );
		
		if( tmp> dp[u][0] ){
			dp[u][1]= dp[u][0]; pos[u][1]= pos[u][0];
			dp[u][0]= tmp; pos[u][0]= v;
		}
		else if( tmp> dp[u][1] ){
			dp[u][1]= tmp; pos[u][1]= v;
		}
	}
	return dp[u][0];
}

void bfs( int rt ){
	for( int i= 0; i<= n; ++i ) flag[i]= 0;
	int head= 0, tail= 0; que[0]= rt; flag[rt]= 1;
	
	while( head<= tail ){
		int u= que[head++];
		
		for( Edge* p= mat[u]; p; p= p->next )
		if( !flag[p->adj] ){
			int v= p->adj, w= p->wt;
			flag[v]= 1; que[++tail]= v;
			
			if( pos[u][0]== v ) w+= dp[u][1];
			else w+= dp[u][0];
			
			if( w> dp[v][0] ){
				dp[v][1]= dp[v][0]; pos[v][1]= pos[v][0];
				dp[v][0]= w; pos[v][0]= u;
			}
			else if( w> dp[v][1] ){
				dp[v][1]= w; pos[v][1]= u;
			}
		}
	}
}

void build( int L, int R, int rt ){
	if( L== R ){
		tb[rt].Max= tb[rt].Min= dp[L][0]; return; }
	
	int mid= (L+ R)>> 1;
	build( L, mid, rt<<1 ); 
	build( mid+ 1, R, rt<<1|1 );
	
	tb[rt].Max= max( tb[rt<<1].Max, tb[rt<<1|1].Max );
	tb[rt].Min= min( tb[rt<<1].Min, tb[rt<<1|1].Min );
} 

int ansMin, ansMax;
void query( int x, int y, int L, int R, int rt ){
	if( L== x && y== R || L== R ){
		ansMin= min( ansMin, tb[rt].Min );
		ansMax= max( ansMax, tb[rt].Max );
		return;
	}
	
	int mid= (L+ R)>>1;
	if( y<= mid ) query( x, y, L, mid, rt<<1 );
	else if( x> mid ) query( x, y, mid+ 1, R, rt<<1|1 );
	else{
		query( x, mid, L, mid, rt<<1 );
		query( mid+ 1, y, mid+ 1, R, rt<<1|1 );
	}
}

int main(){
	scanf("%d%d",&n,&m ); cnt= -1;
	for( int i= 0; i<= n; ++i ){
		mat[i]= 0; flag[i]= 0;
	}
	
	for( int i= 2; i<= n; ++i ){
		int x, y;
		scanf("%d%d",&x,&y);
		add( i, x, y );
	}
	
	dfs(1);  bfs(1);  build(1,n,1);
	
	int head= 1, tail= 1, ans= 1;
	ansMax= dp[1][0], ansMin= dp[1][0];
	while( head<= tail && tail<= n ){
		if( ansMax- ansMin<= m ){
			ans= max( ans, tail- head+ 1 );
			
			tail++;
			ansMax= max( ansMax, dp[tail][0] );
			ansMin= min( ansMin, dp[tail][0] );
		}
		else{
			++head;
			ansMin= inf, ansMax= -inf;
			query( head, tail, 1, n, 1 );
		}
		
		if( n- head+ 1< ans ) break;
	}
	printf("%d\n", ans );

	return 0;
}