[BZOJ]2500: 幸福的道路

2024-02-23 19:34:58

题解: 题目分为两问求从每个点出发的最长链

　　　　　　　　　求一段连续最长的区间让极差小于m

对于第一问显然是树dp 我们考虑对于一个点的最长路径要么从父亲出发要么是从儿子出发这就是我们所谓的 "上搞搞下搞搞" 很显然的我们只需要维护从父亲走的最长路和从儿子走的最长路取max即可我们设从儿子走的最长路径为maxx 从父亲走的最长路径为fmaxx 但是存在一种情况设 y是x的父亲节点它存在 maxx[y]=maxx[x]+x到y的边权但这样的话你去更新fmaxx[x]时就不能用最长儿子路径去更新因为子树路径会走重复所以我们用次大子树路径去更新最大儿子路径的fmaxx 总之我们需要维护三个变量从父亲走的最长路径 fmaxx 从儿子走的最长路径 maxx 从儿子走的次长路径 cmaxx

对于第二问单调队列是可以直接做的(但是基本没写过单调队列) 我写的是倍增ST表双指针扫过去

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
#define ll long long
const int MAXN=1e6+10;
const double eps=1e-8;
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}

int maxx[MAXN],cmaxx[MAXN],a[MAXN];
void dfs1(int x,int fa){
    link(x){
	dfs1(j->t,x);
	if(maxx[x]<maxx[j->t]+j->v)cmaxx[x]=maxx[x],maxx[x]=maxx[j->t]+j->v;
	else if(cmaxx[x]<maxx[j->t]+j->v)cmaxx[x]=maxx[j->t]+j->v;
    }
}

int fmaxx[MAXN];
void dfs2(int x,int fa){
    a[x]=max(maxx[x],fmaxx[x]);
    link(x){
	int temp=(maxx[x]==maxx[j->t]+j->v?cmaxx[x]:maxx[x]);
	temp=max(temp,fmaxx[x]);
	fmaxx[j->t]=temp+j->v;
	dfs2(j->t,x);
    }
}

int dp1[MAXN][21],dp2[MAXN][21];
int ma[MAXN];

int get_max(int l,int r){
    int k=r-l+1;
    k=ma[k];
    return max(dp1[l][k],dp1[r-(1<<k)+1][k]); 
}

int get_min(int l,int r){
    int k=r-l+1;
    k=ma[k];
    return min(dp2[l][k],dp2[r-(1<<k)+1][k]);
}
int n;int m;
bool check(int l,int r){
    if(get_max(l,r)-get_min(l,r)<=m)return 1;
    return 0;
}

int main(){
    ma[1]=ma[0]=0;
    inc(i,2,MAXN-1)ma[i]=ma[i/2]+1;
    n=read();m=read();
    int u;int k;
    inc(i,2,n)u=read(),k=read(),add(u,i,k);
    dfs1(1,0);dfs2(1,0);
    inc(i,1,n)dp1[i][0]=dp2[i][0]=a[i];
    inc(j,1,20){
	for(int i=1;i+(1<<j)<=n+1;i++){
	    dp1[i][j]=max(dp1[i][j-1],dp1[i+(1<<(j-1))][j-1]);
	    dp2[i][j]=min(dp2[i][j-1],dp2[i+(1<<(j-1))][j-1]);
	}
    }
    int tot=1;int ans=0;
    inc(i,1,n){
	while(tot<=n&&check(i,tot))tot++;
	ans=max(ans,tot-i);
    }
    printf("%d\n",ans);
}

2500: 幸福的道路

Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 535 Solved: 219
[Submit][Status][Discuss]

Description

小T与小L终于决定走在一起,他们不想浪费在一起的每一分每一秒,所以他们决定每天早上一同晨练来享受在一起的时光. 他们画出了晨练路线的草图,眼尖的小T发现可以用树来描绘这个草图. 他们不愿枯燥的每天从同一个地方开始他们的锻炼,所以他们准备给起点标号后顺序地从每个起点开始(第一天从起点一开始,第二天从起点二开始……). 而且他们给每条道路定上一个幸福的值.很显然他们每次出发都想走幸福值和最长的路线(即从起点到树上的某一点路径中最长的一条). 他们不愿再经历之前的大起大落,所以决定连续几天的幸福值波动不能超过M(即一段连续的区间并且区间的最大值最小值之差不超过M).他们想知道要是这样的话他们最多能连续锻炼多少天(hint:不一定从第一天一直开始连续锻炼)? 现在，他们把这个艰巨的任务交给你了!

Input

第一行包含两个整数N, M(M<=10^9). 第二至第N行,每行两个数字Fi , Di, 第i行表示第i个节点的父亲是Fi,且道路的幸福值是Di.

Output

最长的连续锻炼天数

Sample Input

3 2
1 1
1 3

Sample Output

3
数据范围：
50%的数据N<=1000
80%的数据N<=100 000
100%的数据N<=1000 000

码农公寓