反思---树上LIS
题目描述
给你一棵 n个节点的树，树的每个节点上都有一个值 a[i] 。
现在要您求出从 1 号点到 i 号点的最短路径上最长上升子序列的长度。
就是单调栈优化+dfs回溯
对比两段代码的dfs部分:
//AC Code
inline void dfs(int u,int f){
int w=lower_bound(b+1,b+l+1,a[u])-b;
int tmpl=l,tmpx=b[w];
b[w]=a[u];
if(w>l) ++l;
ans[u]=l;
for(auto v:G[u]){
if(v==f) continue;
dfs(v,u);
}
l=tmpl,b[w]=tmpx;//回溯回未访问到u的状态
}
//68pts
inline void dfs(int u,int f){
int w=lower_bound(b+1,b+l+1,a[u])-b;
b[w]=a[u];
if(w>l) ++l;
ans[u]=l;
int tmpl=l,tmpx=b[w];
for(auto v:G[u]){
if(v==f) continue;
dfs(v,u);
l=tmpl,b[w]=tmpx;//回溯回访问到u,未访问v的状态
}
}
Q:同样表示还原状态,两者得分为何不同？
A:第二份代码其实没有将 访问v 对b数组的修改 还原(而只是保证了u对b数组的修改)
Ref:图上dfs需要回溯时尽量只涉及一个点的影响