好题。。
先找出每个节点的树上最长路
由树形DP完成
节点x,设其最长路的子节点为y
对于y的最长路,有向上和向下两种情况:
down:y向子节点的最长路g[y][0]
up:x的次长路的g[x][1]+dis[x][y]
up:up[fa[x]]+dis[x][y]
dfs1找向下,即向子节点的最长路
dfs2找向上的最长路
最后最长路f[i]=max(up[x],g[x][0])
第二部分
找最长连续子序列,使得序列中abs(mx-mn)<=m
这次学习了用单调队列的做法
两个队列mx,mn
mx存单减的f[i]的i,mn单增
由于差值不大于m
每次找出front的最小值出队就行了
#include<stdio.h> #include<string.h> #include<algorithm> #include<queue> #define LL long long using namespace std; ; struct node{ int to,next; LL cost; }e[maxn]; int n,m,tot,x; LL g[maxn][],f[maxn],y,head[maxn]; void insert(int u, int v, LL c){ e[++tot].to=v; e[tot].next=head[u]; head[u]=tot; e[tot].cost=c; } #define v e[i].to void dfs1(int u){ ; i=e[i].next){ dfs1(v); ]<g[v][]+e[i].cost){ g[u][]=max(g[u][],g[u][]); g[u][]=g[v][]+e[i].cost; }]=max(g[u][],g[v][]+e[i].cost); } } void dfs2(int u){ ; i=e[i].next){ f[v]=f[u]+e[i].cost; ]+e[i].cost==g[u][]) f[v]=max(f[v],g[u][]+e[i].cost); ]+e[i].cost); dfs2(v); } } int main(){ scanf("%d%d", &n, &m); tot=; memset(head,-,sizeof(head)); ; i<=n; i++){ int x; LL y; scanf("%d%lld", &x, &y); insert(x,i,y); } dfs1(); dfs2(); ; i<=n; i++) f[i]=max(f[i],g[i][]); deque<int> mx,mn; ; ; ; i<=n; i++){ while (!mx.empty() && f[mx.back()]<=f[i]) mx.pop_back(); while (!mn.empty() && f[mn.back()]>=f[i]) mn.pop_back(); mx.push_back(i); mn.push_back(i); while (f[mx.front()]-f[mn.front()]>m){ if (mx.front()<mn.front()){ st=mx.front()+; mx.pop_front(); } else{ st=mn.front()+; mn.pop_front(); } } ans=max(ans,i-st+); } printf("%d\n", ans); ; }