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);