微网站 制作平台_大连小程序定制_百度问一问免费咨询_制作一个网站的费用是多少

闲话

花了一个小时。

主要原因：条初始值硬控我半小时，题目看错硬控我半小时（悲）。

正文

看题目，就是求从哪个点出发所得到的所有单调下降序列的总长度最长(这个描述好奇怪，不过意思是对的)。

题目中说的是树，但其实可以当做图来做，因为题目中提到的是"节点"而与父亲儿子节点无关，也就是说儿子节点也可以访问父亲节点。

大题思路：先输入，其中若有一条边( $1$ , $2$ )，则在 $1$ 与 $2$ 的边中都要加入它。

然后就是求最大值。

如何求最大值呢，其实每个点的最大值就是其所有值小于其本身的点的最大值的总和。然后再求每个点的最大值就可以了。

另外还要加个记忆化，记录每个点的答案的最大值，再打擂台即可A。

总感觉我的方法过于非主流。

AC代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N=5e4+1;
vector<ll> t[N];
ll n,x,a,b,last_ans;
ll ans[N];ll work(ll 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){scanf("%lld",&x);t[i].push_back(x);}for(ll i=1;i<n;++i){scanf("%lld%lld",&a,&b);t[a].push_back(b);t[b].push_back(a);}for(ll i=1;i<=n;++i) if(!ans[i]) ans[i]=work(i);for(ll i=1;i<=n;++i) last_ans=max(last_ans,ans[i]);printf("%lld\n",last_ans);return 0;
}

字数统计：1145