bob的race

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 =  + ;
const int INF = INT_MAX/ -;
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 = ;//最好厘清楚葉子節點,防止有特殊情況發生.
    dp_m[u] = -INF;//初始化,嚴格區分m和s
    dp_s[u] = -INF;
    REP(i, , G[u].size())
    {
        int v = G[u][i].to, len = G[u][i].len;
        if(v!=fa)
        {
            flag = ;
            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==)//葉子節點
    {
        dp_m[u] = ;
    }
}

void getAns_dfs(int u, int fa, int pre_len)//pre_len指的是fa到u的長度,友善下面使用.
{
    ans[u] = ;//ans就是砍掉u的兒子u往上面發出的最大長度
    int &f = ans[u];
    if(fa == )//最根的根節點是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, , 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 = * + ;

int high[T_MAX], low[T_MAX];

void pushUp(int rt)
{
    int lRt = (rt*), rRt = lRt+;
    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][];
int dp2[maxn][];
int mm[maxn];//mm是代表長度對應的二的幂次,1-0,2-1,3-1,4-2
void initRMQ(int n)
{
    mm[] = -;//0是-1,這樣1就是0了
    for(int i = ; i <= n; i++)//算出mm和初始化dp[i][0]
    {
        mm[i] = ((i&(i-)) == )?mm[i-]+:mm[i-];
        dp1[i][] = a[i];
        dp2[i][] = a[i];
    }
    for(int j = ; j <= mm[n]; j++)//長度為2,4,8...
        for(int i = ; i + (<<j) -  <= n; i++)//枚舉起始為1,2,3....
        {
            dp1[i][j] = max(dp1[i][j-],dp1[i + (<<(j-))][j-]);//起始為i,長度幂次j,那麼就是分成起始i,長度幂次j-1,起始i+(1<<(j-1)),長度幂次j-1.
            dp2[i][j] = min(dp2[i][j-],dp2[i + (<<(j-))][j-]);
        }
}
int rmq(int x,int y)//查詢
{
    int k = mm[y-x+];//首先搞出長度幂次.
    return max(dp1[x][k],dp1[y-(<<k)+][k]) - min(dp2[x][k],dp2[y-(<<k)+][k]);//弄的時候要重複一點保證長度是真的幂次,x長度幂次k,y-(1<<k)+1長度幂次k.
}
void solve()
{
    dfs(, );
    getAns_dfs(, , );
    //initail(1, 1, n);
    REP_D(i, , 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 = ;
        int id = ;//很關鍵,标準的尺寸法,for枚舉右端點,id搞左端點
        for(int i = ; i <= n; i++)
        {
            while(id <= i && rmq(id,i) > Q)id++;//找到對應i的最好的id
            ans = max(ans,i-id+);
        }
        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, , n)
        {
            G[i].clear();
        }
        REP_D(i, , n - )
        {
            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 ;
}