POJ 3162 Walking Race 树形DP+线段树

给出一棵树，编号为1~n,给出数m

漂亮mm连续n天锻炼身体，每天会以节点i为起点，走到离i最远距离的节点

走了n天之后，mm想到知道自己这n天的锻炼效果

于是mm把这n天每一天走的距离记录在一起，成为一段长度为n的数列

现在mm想要从这数列中选出一个连续的区间，要求这个区间的max-min<=m

输出最长的区间

做了一个下午

思路：

分成2个部分：

1.求出数列，即对于一棵树，求出每一个节点能到达的最远距离

2.对于这段数列，选出一个区间，使得区间的max-min<=m，并且使得区间长度尽量长。

对于第1部分，其实就是我昨天做的题目，HDU2196，使用树形DP

dp[i][1]:表示从i出发到i的子树，能到达的最远距离

dp[i][2]:表示从i出发到i的子树，能到达的第二远的距离(求dp[i][0]的时候需要用到)

dp[i][0]:表示从i出发，经过i的父亲节点，能到达的最远距离

4次dfs，分别求出：

0.节点的depth，以便把边权(u,v)转化为u,v中depth较大的节点的点权，cost[root]=0;

1.求出dp[i][1]和son[i],son[i]表示dp[i][1]是通过子节点son[i]这道路径得到的

2.求出dp[i][2]

3.求出dp[i][0]

完成第一部分

第二部分，前段时间也做过类似的题，HDU5289

5289要求的是数列中有多少个区间满足条件，我是用RMQ+二分

这道求的是满足条件的最长区间长度

我主要时间是花在了解决第二部分

我刚开始也是用RMQ+二分

发现mle了

因为5289的长度n<=1e5,而这道，n<=1e6，所以RMQ开了会mle

然后我就想改为用线段树代替RMQ的作用，用线段树维护区间的最大值和最小值也很方便，还可以省下很多空间

然后，tle了

原因：

这道题和5289不同的是，这道题不用枚举每一个区间，判断到底满不满足要求

只要求出一个满足的最长的就好啦

然后把枚举左端点+二分右端点的代码注释了

换了种方式：

用2个指针l，r，

若区间[l,r]满足条件，r++，同时更新答案

若不满足条件，l++，直到[l,r]满足条件

复杂度O(n)

这就是传说中的尺取法？

这过程我还犯了一个及其严重的错误:

求最大值的时候，没有把max_ret初始化为-inf

求最小值的时候，没有把min_ret初始化为inf

又花了不少时间

然后终于过了

 #include<cstdio>

 #include<cstring>

 using namespace std;

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 inline int max(int a,int b)

 {

     return a>b?a:b;

 }

 inline int min(int a,int b)

 {

     return a<b?a:b;

 }

 const int maxn=1e6+;

 const int inf=0x3f3f3f3f;

 struct Edge

 {

     int to,next;

 };

 Edge edge[maxn<<];

 int head[maxn];

 int tot;

 int son[maxn];

 int dp[maxn][];

 int e[maxn][];

 int dep[maxn];

 int cost[maxn];

 int seg_max[maxn<<];

 int seg_min[maxn<<];

 int max_ret;

 int min_ret;

 void init()

 {

     memset(head,-,sizeof head);

     tot=;

     memset(dep,,sizeof dep);

     memset(dp,,sizeof dp);

     memset(son,-,sizeof son);

 }

 void addedge(int u,int v)

 {

     edge[tot].to=v;

     edge[tot].next=head[u];

     head[u]=tot++;

 }

 void solve(int n,int m);

 void dfs0(int u,int pre);

 void dfs1(int u,int pre);

 void dfs2(int u,int pre);

 void dfs3(int u,int pre);

 void build(int l,int r,int rt);

 void pushup(int rt);

 int query(int L,int R,int n);

 void query_ret(int L,int R,int l,int r,int rt);

 int main()

 {

     int n,m;

     while(~scanf("%d %d",&n,&m))

     {

         init();

         for(int i=;i<=n;i++)

         {

             int u,v;

             scanf("%d %d",&e[i][],&e[i][]);

             addedge(i,e[i][]);

             addedge(e[i][],i);

         }

         solve(n,m);

     }

     return ;

 }

 void solve(int n,int m)

 {

     dfs0(,-);

     cost[]=;

     for(int i=;i<=n;i++)

     {

         if(dep[i]>dep[e[i][]])

             cost[i]=e[i][];

         else

             cost[e[i][]]=e[i][];

     }

     dfs1(,-);

     dfs2(,-);

     dfs3(,-);

     build(,n,);

     /*

     for(int i=1;i<=n;i++)

     {

         printf("%d\n",max(dp[i][0],dp[i][1]));

     }

     */

     /*

     int ans=0;

     for(int i=1;i<=n;i++)

     {

         int l=i,r=n;

         while(r-l>1)

         {

             int mid=(l+r)>>1;

             if(query(i,mid,n)>m)

                 r=mid;

             else

                 l=mid;

         }

         if(query(i,r,n)<=m)

             ans=max(ans,r-i+1);

         else

             ans=max(ans,l-i+1);

     }

     */

     int ans=;

     int l=,r=;

     while(r<=n)

     {

         while(l<=r&&query(l,r,n)>m)

         {

             l++;

         }

         while(r<=n&&query(l,r,n)<=m)

         {

             ans=max(ans,r-l+);

             r++;

         }

     }

     printf("%d\n",ans);

     return ;

 }

 void dfs0(int u,int pre)

 {

     for(int i=head[u];~i;i=edge[i].next)

     {

         int v=edge[i].to;

         if(v==pre)

             continue;

         dep[v]=dep[u]+;

         dfs0(v,u);

     }

 }

 void dfs1(int u,int pre)

 {

     for(int i=head[u];~i;i=edge[i].next)

     {

         int v=edge[i].to;

         if(v==pre)

             continue;

         dfs1(v,u);

         if(dp[v][]+cost[v]>dp[u][])

         {

             dp[u][]=dp[v][]+cost[v];

             son[u]=v;

         }

     }

 }

 void dfs2(int u,int pre)

 {

     for(int i=head[u];~i;i=edge[i].next)

     {

         int v=edge[i].to;

         if(v==pre)

             continue;

         dfs2(v,u);

         if(v==son[u])

             continue;

         if(dp[v][]+cost[v]>dp[u][])

         {

             dp[u][]=dp[v][]+cost[v];

         }

     }

 }

 void dfs3(int u,int pre)

 {

     for(int i=head[u];~i;i=edge[i].next)

     {

         int v=edge[i].to;

         if(v==pre)

             continue;

         if(v==son[u])

         {

             dp[v][]=max(dp[u][],dp[u][])+cost[v];

         }

         else

         {

             dp[v][]=max(dp[u][],dp[u][])+cost[v];

         }

         dfs3(v,u);

     }

 }

 void pushup(int rt)

 {

     seg_max[rt]=max(seg_max[rt<<],seg_max[rt<<|]);

     seg_min[rt]=min(seg_min[rt<<],seg_min[rt<<|]);

 }

 void build(int l,int r,int rt)

 {

     if(l==r)

     {

         seg_max[rt]=seg_min[rt]=max(dp[l][],dp[l][]);

         return ;

     }

     int m=(l+r)>>;

     build(lson);

     build(rson);

     pushup(rt);

 }

 int query(int L,int R,int n)

 {

     max_ret=-inf;

     min_ret=inf;

     query_ret(L,R,,n,);

     return max_ret-min_ret;

 }

 void query_ret(int L,int R,int l,int r,int rt)

 {

     if(L<=l&&R>=r)

     {

         max_ret=max(max_ret,seg_max[rt]);

         min_ret=min(min_ret,seg_min[rt]);

         return ;

     }

     int m=(l+r)>>;

     if(L<=m)

         query_ret(L,R,lson);

     if(R>m)

         query_ret(L,R,rson);

 }

巴特西

POJ 3162 Walking Race 树形DP+线段树

最新文章

热门文章