SRM666 div1 easy WalkOverATree

考えたこと

• この間勉強した全方位木DPを思い出す
• 頂点数n<=50なのでただの木DPでO(n^2)でいい
• 頂点iの部分木の頂点を全部訪れるのにかかる手数は一番深いところを後回しにすればいいので簡単に求まる
• 頂点iの部分木の頂点を全部訪れるわけではないので dp[i][j] = (頂点iの部分木でjstepのときに行ける最大の頂点数) みたいなのをやろうとする
• 頂点iに戻ってくるのかとかDPの遷移とか考えてると頭がバグる
• 冷静になって考え直すと頂点1個に新たに進むには行って戻って2step必要で頂点0から最も遠い深い葉までの経路についてだけ進むだけでよいので1stepでok
• 最も深い頂点の深さをmaxとすると、(L-max)/2 + max + 1 が答え
• L < max とか Lが大きくて頂点数nを超える場合とかに気をつけつつ出すと通る

無駄に難しく考えすぎた
サンプルがやさしい

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

VI g[100];
int depth[100];
class WalkOverATree {
   public:
   int maxNodesVisited(vector <int> parent, int L)
  {
    function<void(int,int,int)> dfs = [&](int v, int p, int d) {
      depth[v] = d;
      for(int &to: g[v]) if(to != p) {
        dfs(to, v, d+1);
      }
    };

    REP(i, 100) g[i].clear();
    int n = parent.size();
    REP(i, n) {
      g[parent[i]].PB(i+1);
      g[i+1].PB(parent[i]);
    }

    dfs(0, -1, 0);
    int ma = -1;
    REP(i, n+1) {
      chmax(ma, depth[i]);
      // cerr << depth[i] << " ";
    }
    // cerr << endl;

    if(ma >= L) return min(n+1, L + 1);
    return min(n+1, (L-ma)/2 + ma + 1);
  }
};