TopCoder 13955《WalkOverATree》

七月 31, 2019 4145

Problem Statement

Given is a tree on n nodes. The nodes are numbered 0 through n-1. You are given the description of the tree as a int[] parent with n-1 elements. For each valid i, there is an edge between vertices (i+1) and parent[i].

A person is currently standing in node 0. In a single step, the person can move from its current node to any adjacent node. You are given an int L. The person is allowed to make at most L steps.

Return the maximum number of nodes the person can visit during the walk. Node 0 (where the walk starts) and the node where the walk ends count as visited. Each visited node is only counted once, even if it is visited multiple times.

Definition

Class: WalkOverATree
Method: maxNodesVisited
Parameters: int[], int
Returns: int
Method signature: int maxNodesVisited(int[] parent, int L)
(be sure your method is public)

Constraints

  • parent will contain between 0 and 49 elements, inclusive.

  • For each i, parent[i] will be between 0 and i, inclusive.

  • L will be between 1 and 100, inclusive.

Examples

请自行到 vjudge 上寻找

解析

英文很好懂，只需人教初二水平（反正我准初三选手看懂了）

题目大意：
给定一棵 n 个点的树，编号 0~n-1。连边方式以输入每个点的父亲给出，对于每个 i，有一条边连接点 (i+1) 和点 father[i]，而且 father[i] 是 (i+1) 的父亲。
有一个人站在点 0，可以向四周走不超过 L 步，求出这个人能经过多少不同的点

这题和 dp 有什么关系吗。。。

这题的难点大概就是 class 的使用和答案统计了吧

class 的使用可以参考这里

答案统计和基本的思路见代码吧

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//
//  TopCoder13955.cpp
//  Title: WalkOverATree
//  Debugging
//
//  Created by HandwerSTD on 2019/7/31.
//  Copyright © 2019 HandwerSTD. All rights reserved.
//

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define rap(a,s,t,i) for (int a = s; a <= t; a += i)
#define basketball(a,t,s,i) for (int a = t; a >= s; a -= i)
#define countdown(s) while (s --> 0)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

typedef long long int lli;

int getint() { int x; scanf("%d", &x); return x; }
lli getll() { long long int x; scanf("%lld", &x); return x; }

class WalkOverATree {
    /**
     *
     * 直接暴力就好了。。。
     * 一遍 DFS 预处理出所有的点的深度（根节点深度为 0）
     * 答案的输出见下
     *
     */
    
private:
    static const int MAXN = 50 + 10;
    static const int MAXL = 100 + 10;
    std::vector<int> head[MAXN];
    int depthWalk[MAXL];
    int maxstep = 0;
    void DFS(int root = 1, int father = 0, int step = 0) {
        depthWalk[root] = step;
        for (int i = 0, siz = (int) head[root].size(); i < siz; ++i) {
            int next = head[root][i];
            if (next == father) continue;
            DFS(next, root, step + 1);
        }
    }
    
public:
    int ans = 0;
    int maxNodesVisited(std::vector<int> father, int L) {
        memset(head, 0, sizeof head);
        maxstep = L;
        int N = (int) father.size() + 1; // 把根节点算上
        for (int i = 0, siz = N - 1; i < siz; ++i) {
            int prev = (i + 1) + 1, next = father[i] + 1;
            // 编号整体加一
            head[prev].push_back(next);
            head[next].push_back(prev);
        }
        DFS();
        ans = *std::max_element(depthWalk + 1, depthWalk + 1 + N);
        if (ans > L) return L + 1; // 能走的最长的路径已经超过了 L，直接返回 L + 1（把根节点算上）
        ans = std::min(N, ans + 1 + (L - ans) / 2);
        // ans + 1：走过的最长路径加上根节点
        // L - ans：剩下能走的路径，不能浪费
        // (L - ans) / 2：需要一半的路径来折返
        // 注意：剩下的 L - ans 这些路径可以在任何地方用来走，不只是用来在最深的点折返
        // 还有一种情况：所有的点都走完了，还有步数
        // 这时候答案就不会再继续累加了
        // 这种情况下 ans 就要对 N 取个 min
        return ans;
    }
};

// 记得最后提交的时候不要带 main 函数

/*
 int main() {
 std::vector<int> fa;
 fa.clear();
 int x = 0;
 while (true) {
 cin >> x;
 if (x == -1) break;
 fa.push_back(x);
 }
 int l = 0;
 cin >> l;
 WalkOverATree wk;
 cout << wk.maxNodesVisited(fa, l) << endl;
 return 0;
 }
 */