CodeForces1065F 树形dp

时间：2023-03-09 22:05:11
CodeForces1065F 树形dp

http://codeforces.com/problemset/problem/1065/F

你有一棵带有n个结点的树，根是结点1。有一个标记，最初在根结点处。你可以将标记移动到其他结点处。假设标记当前所在结点为v，你可以做出以下两种操作：

将标记移动到v子树的任一叶子处。

如果是结点v为叶子，则将标记向根移动不超过 k 次。换句话说，如果 h(v) 为结点 v 的深度 (根的深度为0），你可以将其移动到顶点 to （ to 为 v 祖先） 并且 h(v)−k≤h(to)。

根不是叶子（即使它的度数是 ）。计算最多能访问多少叶子。

输入格式：

第一行包含两个整数 n 和 k (<k<n≤^) --- 树中的顶点数和向上移动的限制。

第二行包含 n-1个整数 第i个整数表示结点i+1的父亲 输入保证树合法，根为1。

输出格式：

输出一个整数，表示可以访问的最大叶子数。

题意

把问题想难了，想在树dp上同时用树状数组维护，然后一波操作把自己骚死了

一个显然的贪心思想是从1开始将所有可以拿的结点全部拿完之后返回1，然后进入下一个结点，这样每次遍历到根节点的结果都是最优的，判断拿结点的方法用树dp操作一下，用dfs进行预处理即可。

#include <map>

#include <set>

#include <ctime>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <sstream>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

inline int read(){int now=;register char c=getchar();for(;!isdigit(c);c=getchar());

for(;isdigit(c);now=now*+c-'',c=getchar());return now;}

#define For(i, x, y) for(int i=x;i<=y;i++)

#define _For(i, x, y) for(int i=x;i>=y;i--)

#define Mem(f, x) memset(f,x,sizeof(f))

#define Sca(x) scanf("%d", &x)

#define Sca2(x,y) scanf("%d%d",&x,&y)

#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define Scl(x) scanf("%lld",&x);

#define Pri(x) printf("%d\n", x)

#define Prl(x) printf("%lld\n",x);

#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();

#define LL long long

#define ULL unsigned long long

#define mp make_pair

#define PII pair<int,int>

#define PIL pair<int,long long>

#define PLL pair<long long,long long>

#define pb push_back

#define fi first

#define se second

typedef vector<int> VI;

const double eps = 1e-;

const int maxn = 1e6 + ;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + ;

int N,M,K;

struct Edge{

    int to,next;

}edge[maxn * ];

int head[maxn],tot;

void init(){

    memset(head,-,sizeof(int) * (N + ));

    tot = ;

}

void addedge(int u,int v){

    edge[tot].next = head[u];

    edge[tot].to = v;

    head[u] = tot++;

}

int dp[maxn],dp2[maxn];

void dfs(int t){

    if(head[t] == -){

        dp[t] = ; dp2[t] = K;

        return;

    }

    dp[t] = ,dp2[t] = ;

    for(int i = head[t]; ~i ; i = edge[i].next){

        int v = edge[i].to;

        dfs(v);

        if(dp2[v]) dp[t] += dp[v];

        dp2[t] = max(dp2[t],dp2[v] - );

    }

}

int sum = ;

void DP(int t,int ans){

    if(head[t] == -){

        ans++;

        sum = max(sum,ans);

    }

    for(int i = head[t]; ~i; i = edge[i].next){

        int v = edge[i].to;

        if(dp2[v]){

            DP(v,ans + dp[t] - dp[v]);

        }else{

            DP(v,ans + dp[t]);

        }

    }

}

int main()

{

    Sca2(N,K); init();

    for(int i = ; i <= N; i ++){

        int u; Sca(u);

        addedge(u,i);

    }

    int root = ;

    dfs();

    DP(,);

    Pri(sum);

    #ifdef VSCode

    system("pause");

    #endif

    return ;

}

相关文章