【ssl 2570】 【树形DP】 【单调队列】 幸福的道路

【ssl 2570】 【树形DP】 【单调队列】 幸福的道路

题目

解题思路

我没过。。。从2020到2022的悲剧，有人看出来的话踢踢我
先用树形DP求出以每个点为起点的最长路径
因为最大差值不能超过m
用单调队列维护区间最小值和最大值
如果超过了，就将日期早的往后

代码

#include<iostream>
#include<cstdio>
using namespace std;
struct lzf{int to,q,nxt;
}f[2000010];
struct node{int j,id;
}d[1000100],d2[1000100];
int n,m,x,y,t,s=1,h=1,z1,z2,ans;
int head[1000010],q1[1000010],q2[1000010];
void add(int x,int y,int q)
{f[++t].to=y;f[t].q=q;f[t].nxt=head[x];head[x]=t;
}
void dp(int fa,int x)  //求往下的最长链和次长链 
{ for (int i=head[x];i;i=f[i].nxt){dp(x,f[i].to);if (d2[f[i].to].j+f[i].q>d2[x].j){d[x]=d2[x];d2[x]=(node){d2[f[i].to].j+f[i].q,f[i].to};}else if (d[f[i].to].j+f[i].q>d[x].j) d[x]=(node){d2[f[i].to].j+f[i].q,f[i].to};}
}
void dfs(int fa,int x,int w)  //用向上走更新最长链和次长链 
{int len;if (x==d2[fa].id) len=d[fa].j+w;else len=d2[fa].j+w;if (len>d2[x].j) d[x]=d2[x],d2[x]=(node){len,fa};else if (len>d[x].j) d[x]=(node){len,fa};for (int i=head[x];i;i=f[i].nxt)if (f[i].to!=fa) dfs(x,f[i].to,f[i].q);
}
int main()
{scanf("%d%d",&n,&m);for (int i=1;i<n;i++){scanf("%d%d",&x,&y); add(x,i+1,y);}dp(0,1);dfs(0,1,0); x=1;for (int i=1;i<=n;i++){while (h<=z1&&d2[q1[z1]].j<=d2[i].j) z1--;  //维护区间最大 while (s<=z2&&d2[q2[z2]].j>=d2[i].j) z2--;  //维护区间最小 q1[++z1]=i,q2[++z2]=i; while (d2[q1[h]].j-d2[q2[s]].j>m)  //维护差值不超过m{if (q1[h]<q2[s]) x=q1[h]+1,h++;else x=q2[s]+1,s++;}ans=max(ans,i-x+1); }printf("%d",ans);return 0;
}