闲话
花了一个小时。
主要原因：条初始值硬控我半小时，题目看错硬控我半小时（悲）。
正文
看题目，就是求从哪个点出发所得到的所有单调下降序列的总长度最长（这个描述好奇怪，不过意思是对的）。
题目中说的是树，但其实可以当做图来做，因为题目中提到的是“节点”，而与父亲儿子节点无关，也就是说儿子节点也可以访问父亲节点。
大体思路：先输入，其中若有一条边 $(1,2)$，则在 $1$ 与 $2$ 的边中都要加入它，也就是当成无向图来做。
然后就是求最大值。
如何求最大值呢，其实每个点的最大值就是其所有值小于其本身的点的最大值的总和。然后再求每个点的最大值就可以了。
另外还要加个记忆化，记录每个点的答案的最大值，再打擂台即可 A。
总感觉我的方法过于非主流。
AC 代码
#include<bits/stdc++.h>//万能头 using namespace std;//标准命名空间 using ll = long long;//【不开longlong见祖宗】，当然这题随便 const ll N=1e5+1;//n<=100000$ vector<ll> t[N];//存储节点、邻接点 ll n,x,a,b;//临时输入变量 ll ans[N],last_ans;//存储答案 ll work(ll i)//计算编号为i的点的答案 { ll not_all=1;//自己算一个节点 for(ll j=1;j<ll(t[i].size());++j)//循环访问与自己有边的节点 if(t[i][0]>t[t[i][j]][0])//严格小于 { if(!ans[t[i][j]]) ans[t[i][j]]=work(t[i][j]);//如果没有计算过就当场计算 not_all+=ans[t[i][j]];//加和计算 } return not_all;//返回该点的值 } int main() { scanf("%lld",&n);//输入节点数 for(ll i=1;i<=n;++i)//是n个点 { scanf("%lld",&x); t[i].push_back(x);//存储自己的值 } for(ll i=1;i<n;++i)//注意是n-1条边，因为是树 { scanf("%lld%lld",&a,&b); t[a].push_back(b);//父亲节点与儿子节点 ，所以存储 t[b].push_back(a);//当成无向图处理 ，所以存储 } for(ll i=1;i<=n;++i)//计算n个点的答案 if(!ans[i])//如果在算其它点时没有算过再计算 ans[i]=work(i);//计算 for(ll i=1;i<=n;++i)//打擂台—— last_ans=max(last_ans,ans[i]);//——求最大值 printf("%lldn",last_ans);//输出 return 0;//完结撒花 } 
