poj 3162 Walking Race

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树dp

题意：给出n个点的无根树，然后其他每个点可以走出的最远距离（从该点出现走出一条最长的简单路径）。然后按顺序排好点1，点2，点3，点4的最远距离，即得到一个序列。给一个限制值m，在序列中找一段最长的连续区间，使得区间内最大值和最小值的差值要<=m，问这样的区间长度是多少

这题主要是求每个点能走出的最远距离，对于后面那个查询最长区间，是怎么做都可以的。

设一个点能走出的最远距离为d[u]，两次dfs即可求出，非常典型的树dp技巧，就不详细说了

对于查询最长区间，就是使用双指针的方法，一开始都指向1，然后询问一些双指针包括的区间，查询一些区间的最大和最小值，如果差<=m，那么说明这个区间是合法的，尝试去更新答案，并且将尾指针向右移动，因为显然可以尝试去增加长度。如果差 > m，那么说明这个区间不合法，将头指针向右移动。所以解决的主要问题就是每次都要询问区间的最大值和最小值，这个，可以用RMQ，但是这题，数据太大，RMQ的dp数组开下去会MLE，所以就用什么？没错暴力…………

网上很多报告都说线段树和单调队列，确定单调队列应该是最快的，但是线段树未免小题大做了，速度非常慢，比暴力慢多了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define N 1000010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define lson(i) ((i)<<1)
#define rson(i) ((i)<<1|1)

int n,tot,head[N]; int m;
struct edge{
	int v,w,next;
	edge(){}
	edge(int __v,int __w){
		v = __v; w = __w;
	}
}e[2*N];
int leaf[N][2]; 
int id[N][2];
int back[N],d[N];
int Pow[21];

inline void add(int u ,int v,int w){
	e[tot] = edge(v,w);
	e[tot].next = head[u]; head[u] = tot++;
}

void dfs1(int u,int fa){
	leaf[u][0] = leaf[u][1] = 0; 
	id[u][0] = id[u][1] = -1;
	for(int k = head[u]; k != -1; k = e[k].next){
		int v = e[k].v;
		int w = e[k].w;
		if(v == fa) continue;
		dfs1(v,u);
		if(leaf[v][0] + w > leaf[u][0]){
			leaf[u][1] = leaf[u][0]; id[u][1] = id[u][0];
			leaf[u][0] = leaf[v][0] + w; id[u][0] = v;
		}
		else if(leaf[v][0] + w > leaf[u][1]){
			leaf[u][1] = leaf[v][0] + w; id[u][1] = v;
		}
	}
}

void dfs2(int len,int u,int fa){
	if(fa != -1){
		int res = 0;
		res = max(res,len + back[fa]);
		if(id[fa][0] != -1 && id[fa][0] != u){
			res = max(res, len + leaf[fa][0]);
		}
		else if(id[fa][1] != -1 && id[fa][1] != u){
			res = max(res , len + leaf[fa][1]);
		}
		back[u] = res;
		d[u] = max(back[u],leaf[u][0]);
	}
	for(int k = head[u]; k != -1; k = e[k].next){
		int v = e[k].v;
		int w = e[k].w;
		if(v == fa) continue;
		dfs2(w , v , u);
	}
}

inline int getmax(int a,int b){
	int res = -(1<<30);
	for(int i = a; i <= b; i++)
		res = max(res,d[i]);
	return res;
}
inline int getmin(int a,int b){
	int res = (1<<30);
	for(int i = a; i <= b; i++)
		res = min(res,d[i]);
	return res;
}

int main(){
	for(int i = 0; i <= 20; i++) Pow[i] = (1<<i);
	while(scanf("%d%d",&n,&m)!=EOF){
		cl(head,-1); tot = 0;
		for(int u = 2; u <= n; u++){
			int v; int w;
			scanf("%d%d",&v,&w);
			add(u,v,w); add(v,u,w);
		}
		dfs1(1,-1);
		back[1] = 0; d[1] = leaf[1][0];
		dfs2(0,1,-1);
		//for(int i = 1; i <= n; i++)
		//	printf("%d : %d %d %d %d\n",i,leaf[i][0],leaf[i][1],back[i],d[i]);
		
		//build(1,1,n);
		
		int left = 1 , right = 1 , ans = 0;
		while(right <= n){
			int res1 = getmax(left,right);
			int res2 = getmin(left,right);
			if(res1 - res2  <= m){
				ans = max(ans,right-left+1);
				right++;
			} 
			else left++;
			if(n-left+1 <= ans) break;
		}
		printf("%d\n",ans);
	}
	return 0;
}

线段树的代码，只给出建树和查询部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
struct SegTree{
	int l,r,mid,Max,Min;
	SegTree(){}
	SegTree(int __l,int __r){
		l = __l; r = __r; mid = (l+r)>>1;
	}
}t[N<<2];

void build(int rt,int a, int b){
	t[rt] = SegTree(a,b);
	if(a == b){
		t[rt].Max = t[rt].Min = d[a];
		return ;
	}
	int mid = t[rt].mid;
	build(lson(rt),a,mid);
	build(rson(rt),mid+1,b);
	t[rt].Max = max(t[lson(rt)].Max , t[rson(rt)].Max);
	t[rt].Min = min(t[lson(rt)].Min , t[rson(rt)].Min);
}

int query(int rt,int a,int b,int k){
	if(t[rt].l == a && t[rt].r == b){
		if(k) return t[rt].Max;
		else return t[rt].Min;
	}
	int mid = t[rt].mid;
	if(b <= mid) return query(lson(rt),a,b,k);
	else if(a > mid) return query(rson(rt),a,b,k);
	else{
		if(k) return max(query(lson(rt),a,mid,k) , query(rson(rt),mid+1,b,k));
		else  return min(query(lson(rt),a,mid,k) , query(rson(rt),mid+1,b,k));
	}
}

build(1,1,n);
int left = 1 , right = 1 , ans = 0;
while(right <= n){
        int res1 = query(1,left,right,1); //getmax(left,right);
	int res2 = query(1,left,right,0); //getmin(left,right);
	if(res1 - res2  <= m){
	        ans = max(ans,right-left+1);
		right++;
	} 
	else left++;
	if(n-left+1 <= ans) break;
}
printf("%d\n",ans);