首页 > 其他分享 >Codeforces Round #831 (Div. 1 + Div. 2) E

Codeforces Round #831 (Div. 1 + Div. 2) E

时间:2022-10-30 00:33:56浏览次数:58  
标签:831 const int ans1 sum Codeforces Div 节点

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

相关文章

  • Codeforces Round #831 (Div. 1 + Div. 2)
    A.FactoriseN+M题意:给出一个质数,求另一个质数,使得两个数之和不是质数。解:把那个质数再输出一遍就行了。B.JumboExtraCheese2题意:给出一些长方形,按照以下规则把长......
  • Codeforces Round #750 (Div. 2) F1
    F1.KorneyKorneevichandXOR(easyversion)我们观察题意发现我们需要找的是一个上升序列我们回忆上升序列的状态设计dp[i]表示第i个作为结尾最长的序列长度是多少......
  • Educational Codeforces Round 93 (Rated for Div. 2) D
    D.ColoredRectangles考虑数据范围显然可以n3dp我们发现dp转移时不是特别好枚举所以我们选择记忆化搜索打完你们可能会发现过不去第三个样例显然我们应该sort一遍......
  • Codeforces Round #827 (Div. 4) A-G
    比赛链接A题解知识点:模拟。时间复杂度\(O(1)\)空间复杂度\(O(1)\)代码#include<bits/stdc++.h>#definelllonglongusingnamespacestd;boolsolve(){......
  • Educational Codeforces Round 1
    EducationalCodeforcesRound1C.Nearestvectors题目大意给出n个向量,求出其中夹角最小的两个向量。分析求出所有向量与x轴的夹角,然后排序,两两比较夹角。AC_code#......
  • Codeforces Round #826 (Div. 3) A-E
    比赛链接A题解知识点:模拟。时间复杂度\(O(n)\)空间复杂度\(O(n)\)代码#include<bits/stdc++.h>#definelllonglongusingnamespacestd;boolsolve(){......
  • Codeforces Round #830 (Div. 2)(持续更新)
    PrefaceAB很水,C一般难度,D1很简单但D2确实巧妙没有现场打有点可惜,后面补的时候都是1A(结果每次比赛的时候都要莫名WA上好久)A.Bestie我刚开始没咋想,感觉操作步数不会很......
  • Codeforces Round #739 (Div. 3) E
    E.PolycarpandStringTransformation显然我们可以通过看谁消失的最早知道删除序列然后有了删除序列以后我们能干什么呢显然对于每一个删除序列我们要是第一次就把......
  • Codeforces Round #672 (Div. 2) D
    D.RescueNibel!转化题意就是叫我们求k条线段都有重合的方案数最开始想的是离散化+线段树手模拟一下样例这样会是有重复的我们要如何保证不重不漏!显然我们可以将线......
  • Codeforces Round #631 (Div. 1) - Thanks, Denis aramis Shitov! A
    A.DreamoonLikesColoring显然我们不看把整块涂满最优的构造就是1234....但是要考虑将整块板涂满我们就要往右挪显然我们每次挪后面的板子都会动我们一定要让......