bob的race

原创
2015/05/26 11:17
阅读数 80

HUD4123 Bob’s Race

题目描述:

首先给出一棵树,n~5e4,然后要求求出每个点出发走不重复路径到达的最远的距离.之后,找出最长的连续的节点的长度,使得他们的之中最大值减去最小值小于等于给出的Q.一共问了M~500次Q.

题解:

完全分为两部分:先求出每个点最远到达长度.常用的树形dp.首先一次dp出节点u为根的dpm和dps,保证这两个没有相交的路径.之后再dfs出u,含义是u往上身的最长长度,即是说把u的儿子们都砍了,以u出发的最长长度.这个是dp的关键,就是u,fa,fa_len,那么u的长度可能是先到fa,再用dp[fa],也可能先到fa再用fa的子树,并且这个子树不能是u删掉的那些. 两次dfs完了之后,取大就好.
第二部分,分别搞到每个a[i],求相差小于Q的最大长度. 首先这样一定是尺寸法,下面有一个标准的尺寸法的写法.然后怎么判定?可以用两个单调队列来维护,这个方法很好很直观.也可以用RMQ直接查询最大值和最小值.下面用RMQ来实现,顺便固定下RMQ的姿势

重点:

(1)树形dp求树上每一个点跑到最远的长度.(2)给出数组用尺寸法求出连续的相差小于等于Q的最大长度.

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <ctype.h>
#include <limits.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <bitset>
#define CLR(a) memset(a, 0, sizeof(a))
#define REP(i, a, b) for(int i = a;i < b;i++)
#define REP_D(i, a, b) for(int i = a;i <= b;i++)

typedef long long ll;

using namespace std;

const int maxn = 5e4 + 100;
const int INF = INT_MAX/2 -1;
int ans[maxn], dp_m[maxn], dp_s[maxn];
int n, m;
struct info
{
    int to, len;
};

vector<info> G[maxn];

void dfs(int u, int fa)//第一次dfs
{
    int flag = 0;//最好分清楚叶子节点,防止有特殊情况发生.
    dp_m[u] = -INF;//初始化,严格区分m和s
    dp_s[u] = -INF;
    REP(i, 0, G[u].size())
    {
        int v = G[u][i].to, len = G[u][i].len;
        if(v!=fa)
        {
            flag = 1;
            dfs(v, u);
            int temp = dp_m[v] + len;//只用子树的m来更新,因为如果只有一个儿子,那么因为路径不能够重复,所以u的s应该是-INF的.
            if(temp > dp_m[u])
            {
                dp_s[u] = dp_m[u];
                dp_m[u] = temp;
            }
            else if(temp > dp_s[u])
            {
                dp_s[u] = temp;
            }
        }
    }
    if(flag==0)//叶子节点
    {
        dp_m[u] = 0;
    }
}

void getAns_dfs(int u, int fa, int pre_len)//pre_len指的是fa到u的长度,方便下面使用.
{
    ans[u] = 0;//ans就是砍掉u的儿子u往上面发出的最大长度
    int &f = ans[u];
    if(fa == 0)//最根的根节点是0
    {
        ;
    }
    else
    {
        if(dp_m[fa]!=-INF&&dp_m[fa]==dp_m[u]+pre_len)//如果fa的m正好是坎了
        {
            if(dp_s[fa]!=-INF)
            {
                int temp = dp_s[fa] + pre_len;
                f = max(f, temp);
            }
        }
        if(dp_m[fa]!=-INF&&dp_m[fa]!=dp_m[u]+pre_len)//没有砍
        {
            int temp = dp_m[fa] + pre_len;
            f = max(f, temp);
        }
        f = max(f, ans[fa] + pre_len);//直接上去fa,没有用到fa的子树
    }
    REP(i, 0, G[u].size())
    {
        int len = G[u][i].len, v = G[u][i].to;
        if(v!=fa)
        {
            getAns_dfs(v, u, len);//继续传进去dfs
        }
    }
}
const int T_MAX = 50000*4 + 10;

int high[T_MAX], low[T_MAX];

void pushUp(int rt)
{
    int lRt = (rt*2), rRt = lRt+1;
    high[rt] = max(high[lRt], high[rRt]);
    low[rt] = min(low[lRt], low[rRt]);
}
//void initail(int rt, int l, int r)
//{
   
   
   
//    if(l == r)
//    {
   
   
   
//        high[rt] = ans_m[l];
//        low[rt] = high[rt];
//        //printf("---%d---  %d  ss --- %d\n", l, ans_m[l], ans_s[l]);
//    }
//    else
//    {
   
   
   
//        int mid = (l + r)/2;
//        int lRt = (rt*2), rRt = lRt+1;
//        initail(lRt, l, mid);
//        initail(rRt, mid + 1, r);
//        pushUp(rt);
//    }
//}
//int query_max(int L, int R, int rt, int l, int r)
//{
   
   
   
//    if(L <= l && R >= r)
//    {
   
   
   
//        return high[rt];
//    }
//    int mid = ((l + r)>>1), lRt = (rt<<1), rRt = ((rt<<1)|1);
//    int ans = 0;
//    if(L <= mid)
//    {
   
   
   
//        ans = max(ans, query_max(L, R, lRt, l, mid));
//    }
//    if(R >= mid + 1)
//    {
   
   
   
//        ans = max(ans, query_max(L, R, rRt, mid + 1, r));
//    }
//    return ans;
//}
//int query_min(int L, int R, int rt, int l, int r)
//{
   
   
   
//    if(L <= l && R >= r)
//    {
   
   
   
//        return low[rt];
//    }
//    int mid = (l + r)/2;
//    int lRt = (rt*2), rRt = lRt+1;
//    int ans = INF;
//    if(L <= mid)
//    {
   
   
   
//        ans = min(ans, query_min(L, R, lRt, l, mid));
//    }
//    if(R >= mid + 1)
//    {
   
   
   
//        ans = min(ans, query_min(L, R, rRt, mid + 1, r));
//    }
//    return ans;
//}
int a[maxn];

int dp1[maxn][20];
int dp2[maxn][20];
int mm[maxn];//mm是代表长度对应的二的幂次,1-0,2-1,3-1,4-2
void initRMQ(int n)
{
    mm[0] = -1;//0是-1,这样1就是0了
    for(int i = 1; i <= n; i++)//算出mm和初始化dp[i][0]
    {
        mm[i] = ((i&(i-1)) == 0)?mm[i-1]+1:mm[i-1];
        dp1[i][0] = a[i];
        dp2[i][0] = a[i];
    }
    for(int j = 1; j <= mm[n]; j++)//长度为2,4,8...
        for(int i = 1; i + (1<<j) - 1 <= n; i++)//枚举起始为1,2,3....
        {
            dp1[i][j] = max(dp1[i][j-1],dp1[i + (1<<(j-1))][j-1]);//起始为i,长度幂次j,那么就是分成起始i,长度幂次j-1,起始i+(1<<(j-1)),长度幂次j-1.
            dp2[i][j] = min(dp2[i][j-1],dp2[i + (1<<(j-1))][j-1]);
        }
}
int rmq(int x,int y)//查询
{
    int k = mm[y-x+1];//首先搞出长度幂次.
    return max(dp1[x][k],dp1[y-(1<<k)+1][k]) - min(dp2[x][k],dp2[y-(1<<k)+1][k]);//弄的时候要重复一点保证长度是真的幂次,x长度幂次k,y-(1<<k)+1长度幂次k.
}
void solve()
{
    dfs(1, 0);
    getAns_dfs(1, 0, 0);
    //initail(1, 1, n);
    REP_D(i, 1, n)
    {
        a[i] = max(ans[i], dp_m[i]);//这个a就是最终的结果
        //printf("--%d--%d\n", i, a[i]);
    }
    initRMQ(n);//初始化RMQ,使得好查
    while(m--)
    {
        int Q;
        scanf("%d",&Q);
        int ans = 0;
        int id = 1;//很关键,标准的尺寸法,for枚举右端点,id搞左端点
        for(int i = 1; i <= n; i++)
        {
            while(id <= i && rmq(id,i) > Q)id++;//找到对应i的最好的id
            ans = max(ans,i-id+1);
        }
        printf("%d\n",ans);
    }


//    while(m--)
//    {
   
   
   
//        int q;
//        int a = 0;
//        scanf("%d", &q);
//        int l = 1, r = 1;
//        while(1)
//        {
   
   
   
//            if(r > n || l > n)
//                break;
//            if(query_max(l, r, 1, 1, n)-query_min(l, r, 1, 1, n)<=q)
//            {
   
   
   
//                a = max(a, r - l + 1);
//                r++;
//            }
//            else
//            {
   
   
   
//                l++;
//            }
//        }
//        printf("%d\n", a);
//    }
}

int main()
{
   // freopen("2Bin.txt", "r", stdin);
    //freopen("3Bout.txt", "w", stdout);
    while(scanf("%d%d", &n, &m) != EOF)
    {
        if(!n&&!m)
        {
            break;
        }
        REP_D(i, 1, n)
        {
            G[i].clear();
        }
        REP_D(i, 1, n - 1)
        {
            int a, b, len;
            scanf("%d%d%d", &a, &b, &len);
            info tmp;
            tmp.to = b;
            tmp.len = len;
            G[a].push_back(tmp);
            tmp.to = a;
            G[b].push_back(tmp);
        }
        solve();
    }
    return 0;
}

本文分享 CSDN - ruclion。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部