E. Hanging Hearts
我们观察每一个节点
它可以由其子节点的所有长链来构造
还有就是直接可以由自己构成的一条长链
所以对于每一个节点我们的答案就是max(加上自己的最长链,所有儿子加起来的节点数)
所以我们维护一个加上自己的最长链ans1[]
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 998244353;
const int mod = 1e9+7;
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
vector<int>g[N];
int ans1[N];
int bfs(int u,int fa){
int sum=0;
ans1[u]=1;
for(auto v:g[u]){
if(v==fa)continue;
int t=bfs(v,u);
ans1[u]=max(ans1[u],ans1[v]+1);
sum+=t;
}
sum=max(ans1[u],sum);
return sum;
}
void solve() {
int n;cin>>n;
int flag=1;vector<int>st(n+10);
for(int i=2;i<=n;i++){
int x;cin>>x;st[x]++;
g[i].push_back(x);
g[x].push_back(i);
}
for(int i=1;i<=n;i++)if(st[i]>=2)flag=0;
if(flag)cout<<n<<endl;
else cout<<bfs(1,0)<<endl;
}
signed main(){
fast
int t;t=1;//cin>>t;
while(t--) {
solve();
}
return ~~(0^_^0);
}
标签:831,const,int,ans1,sum,Codeforces,Div,节点
From: https://www.cnblogs.com/ycllz/p/16840309.html