Educational Codeforces Round 52F(树形DP,VECTOR)

#include<bits/stdc++.h>
using namespace std;
int n,k;
vector<int>son[1000007];
int dp[1000007],depth[1000007],ans[1000007];//dp【i】表示离i最近的叶子节点距离i的深度,depth【i】表示以i为根,回到i所能到达的叶子节点的数量,ans【i】表示以i为根,能到达的叶子节点数目最大,即题意所需
void dfs(int now){
    if(!son[now].size()){//本身为叶子结点
        depth[now]=0;
        dp[now]=1;
        return;
    }
    int mn=1e9,mx=0;
    for(const int&tmp:son[now]){//遍历孩子结点
        dfs(tmp);//继续深搜
        if(depth[tmp]<k)//小于k的话从now向下走可以走到孩子结点tmp所能触及的叶子结点
            dp[now]+=dp[tmp];//把孩子能碰到的叶子向上传递给父亲
        mx=max(mx,ans[tmp]-(depth[tmp]<k?dp[tmp]:0));//depth【tmp】<k时,dp【tmp】已经加到了dp【now】里,把它减掉,mx留下的是最大的一次下去回不来所能碰到的叶子结点数
        mn=min(mn,depth[tmp]+1);//now的深度为最小的孩子深度+1
    }
    depth[now]=mn;//mn只放最小的深度,那些子节点深度过大的都碰不到,只会碰一次符合题意的叶子结点(这次下去了就回不到祖先节点(这一次dfs的参数)了)
    ans[now]=dp[now]+mx;//mx只能加一个所以放在循环之外
}
int main(){
    scanf("%d%d",&n,&k);
    int x;
    for(int i=2;i<=n;i++){
        scanf("%d",&x);
        son[x].push_back(i);
    }
    dfs(1);
    printf("%d\n",ans[1]);
    return 0;
}

//可以用数组模拟链表头插法,遍历链表的方式解决,思路相同,储存方式不同而已

上一篇:关于CSS的一些总结


下一篇:最长公共子序列(POJ1458)