P11378[GESP202412 七级]燃烧 题解

闲话

花了一个小时。

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

正文

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

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

大体思路：先输入，其中若有一条边 $(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;//完结撒花  }