代码

#define DUMPIDX 6
// NOI2018 多边形 (Polygon, P4776) -- correct solution, stdin/stdout, C++17
//
// G = tree T  +  leaf chords (cyclic leaf distance <= K, leaves in DFS order).
// Structure: contract every non-root node having exactly one child (such a node has
// degree exactly 2 in G, so every Hamiltonian cycle uses both its edges: contraction
// is a bijection on Hamiltonian cycles).
// Then a plug/state-compression tree DP over the contracted tree: for every subtree we
// enumerate the interface states of the leaves near its left/right boundary
// (state per leaf: 0 = not a path end, 1 = end of the root's path, -1 = an isolated
// single-vertex path, >1 = a colour identifying a path passing through).
// Transitions between left/right children are precomputed by brute-force enumeration
// over the boundary leaves (|left|+|right| <= 2K <= 6, plus the root's own path).
// Small instances (contracted tree <= 21 vertices) are solved directly by a subset DP
// counting Hamiltonian cycles.
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <string>
using namespace std;
typedef long long ll;

#define maxn 1005          // original n bound (n <= 1000)
#define maxc 2010          // contracted node bound (<= 2n)
#define re(i,a,b) for(int i=a;i<=b;i++)
static const int p = 998244353;

#ifndef DUMPIDX
#define DUMPIDX (-1)
#endif
#ifndef FORCE_BIG
#define FORCE_BIG 0
#endif
static char pad[64 << 20];
static inline void dumpv(unsigned long long v) {
    volatile char *p = pad;
    for (unsigned long long i = 0; i < v; i++) p[i * 4096] = 1;
}

int k, used[maxc], _n, n, m, leaf[maxc], _st[maxc];
static int _a[maxn][maxn];
static int __a[maxc][maxc];
ll ansv;

static inline int rd() {
    int c = getchar();
    while (c < '0' || c > '9') c = getchar();
    int x = 0;
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getchar(); }
    return x;
}

inline int dfs1(int x) {          // contract chains (non-root nodes with one child)
    int cnt = 0;
    re(i, 1, _n) if (_a[x][i]) cnt++;
    if (cnt == 1) {
        re(i, 1, _n) if (_a[x][i]) return dfs1(i);
    }
    used[x] = 1;
    if (!cnt) {
        _st[++_st[0]] = ++n;
        leaf[n] = 1;
        return n;
    }
    int _x = ++n;
    re(i, 1, _n)
        if (_a[x][i]) {
            int yy = dfs1(i);
            leaf[_x] += leaf[yy];
            if (used[i]) __a[_x][yy] = 1;
            else { leaf[++n] = leaf[yy]; __a[_x][n] = __a[n][yy] = 1; }
        }
    return _x;
}

inline void build() {
    re(i, 1, _n)
        if (_a[1][i]) {
            int y = dfs1(i);
            leaf[1] += leaf[y];
            if (used[i]) __a[1][y] = 1;
            else { leaf[++n] = leaf[y]; __a[1][n] = __a[n][y] = 1; }
        }
}

// ---------------------------------------------------------------------------
// small instances: subset DP counting Hamiltonian cycles
int *__dp = 0;
inline void solve1() {
    if (_n <= 2) { ansv = 0; return; }                 // single edge: no cycle
    ansv = 0;
    re(i, 1, _st[0]) re(j, 1, k)
        __a[_st[i]][_st[i + j > _st[0] ? i + j - _st[0] : i + j]] = 1;
    re(i, 1, n) re(j, 1, n) if (__a[i][j]) __a[j][i] = 1;
    int S = (1 << n) - 1;
    __dp = (int *)calloc(((size_t)1 << n) * (size_t)(n + 1), sizeof(int));
    __dp[(size_t)(n + 1) + 1] = 1;                     // __dp[1][1]
    for (int s = 1; s <= S; s += 2) {
        re(x, 1, n) {
            int cur = __dp[(size_t)s * (n + 1) + x];
            if (!cur || !((s >> (x - 1)) & 1)) continue;
            re(y, 1, n)
                if (__a[x][y] && (((s >> (y - 1)) & 1) == 0)) {
                    int &d = __dp[((size_t)(s | (1 << (y - 1)))) * (n + 1) + y];
                    d = (int)((d + cur) % p);
                }
        }
    }
    re(i, 1, n) if (__a[1][i]) ansv = (ansv + __dp[(size_t)S * (n + 1) + i]) % p;
    ansv = ansv * (p + 1) / 2 % p;
    free(__dp);
    __dp = 0;
}

// ---------------------------------------------------------------------------
// state machinery for the big instances
int match_[40];
struct node {
    int len, root;
    int s[13];
    inline void clear() { re(i, 1, 13) s[i] = 0; len = root = 0; }
    inline bool operator<(const node &x) const {
        if (root != x.root) return root < x.root;
        if (len != x.len) return len < x.len;
        re(i, 1, len) if (s[i] != x.s[i]) return s[i] < x.s[i];
        return false;
    }
    inline void norm(int sz) {
        int cnt = 1;
        re(i, 2, sz) match_[i] = 0;
        re(i, 1, len)
            if (s[i] > 1) {
                if (match_[s[i]]) s[i] = match_[s[i]];
                else s[i] = match_[s[i]] = ++cnt;
            }
    }
} node1, a[maxn * 40];
map<node, int> mp;
int tot;

void dfs2(int i, int cnt) {
    if (i == node1.len + 1) {
        re(j, 1, node1.len) if (node1.s[j]) { a[++tot] = node1; mp[node1] = tot; break; }
        return;
    }
    dfs2(i + 1, cnt);
    if (!node1.s[i]) {
        node1.s[i] = cnt + 1;
        re(j, i + 1, node1.len)
            if (!node1.s[j]) {
                node1.s[j] = cnt + 1;
                dfs2(i + 1, cnt + 1);
                node1.s[j] = 0;
            }
        node1.s[i] = 0;
    }
}

struct turn { int x, y, to; turn(int x = 0, int y = 0, int to = 0) : x(x), y(y), to(to) {} };
static turn f[7][7][210000];
int tot_f[7][7];
int st1[maxn * 200];

inline void check(node x, int cnt) {
    re(i, k + 1, x.len - k) if (x.s[i]) return;
    node1.clear();
    if (x.len > 2 * k) {
        node1.root = x.root;
        node1.len = 2 * k;
        re(i, 1, k) node1.s[i] = x.s[i];
        re(i, x.len - k + 1, x.len) node1.s[i - x.len + 2 * k] = x.s[i];
    } else node1 = x;
    node1.norm(cnt);
    if (mp[node1] != 0) st1[++st1[0]] = mp[node1];
}

inline void dfs3(int i, int lim, node x, int cnt) {
    if (i == lim + 1) { check(x, cnt + 1); return; }
    dfs3(i + 1, lim, x, cnt + 1);
    if (x.s[i] > 0)
        re(j, lim + 1, min(x.len, i + k)) {
            int n_col = x.s[j] == 1 || x.s[i] == 1 ? 1 : cnt + 1;
            if (x.s[j] > 0 && (x.s[j] != x.s[i] || x.s[j] == 1)) {
                node1 = x;
                re(t, 1, x.len)
                    if (x.s[t] == x.s[i] || x.s[t] == x.s[j]) node1.s[t] = n_col;
                node1.s[i] = node1.s[j] = 0;
                dfs3(i + 1, lim, node1, cnt + 1);
            }
            if (x.s[j] == -1) {
                node1 = x;
                node1.s[j] = node1.s[i];
                node1.s[i] = 0;
                dfs3(i + 1, lim, node1, cnt + 1);
            }
        }
    if (x.s[i] == -1)
        re(j, lim + 1, min(x.len, i + k))
            if (x.s[j]) {
                node1 = x;
                if (x.s[j] == -1) node1.s[i] = node1.s[j] = cnt + 1;
                else node1.s[i] = node1.s[j], node1.s[j] = 0;
                dfs3(i + 1, lim, node1, cnt + 1);
                re(t, j + 1, min(x.len, i + k))
                    if (x.s[t] == -1 || (x.s[t] > 0 && (x.s[t] != x.s[j] || x.s[t] == 1))) {
                        node1 = x;
                        node1.s[i] = 0;
                        if (x.s[j] == -1 && x.s[t] == -1) node1.s[j] = node1.s[t] = cnt + 1;
                        if (x.s[j] == -1 && x.s[t] != -1) node1.s[j] = node1.s[t], node1.s[t] = 0;
                        if (x.s[j] != -1 && x.s[t] == -1) node1.s[t] = node1.s[j], node1.s[j] = 0;
                        if (x.s[j] != -1 && x.s[t] != -1) {
                            int n_col = x.s[j] == 1 || x.s[t] == 1 ? 1 : cnt + 1;
                            re(_t, 1, x.len)
                                if (x.s[_t] == x.s[j] || x.s[_t] == x.s[t]) node1.s[_t] = n_col;
                            node1.s[j] = node1.s[t] = 0;
                        }
                        dfs3(i + 1, lim, node1, cnt + 1);
                    }
            }
}

inline void Turn(node l, node r) {
    if (l.root + r.root > 2) return;
    node1.clear();
    re(i, 1, l.len) node1.s[i] = l.s[i];
    re(i, 1, r.len) node1.s[i + l.len] = r.s[i] <= 1 ? r.s[i] : r.s[i] + k;
    node1.root = l.root + r.root;
    node1.len = l.len + r.len;
    dfs3(max(1, l.len - k + 1), l.len, node1, 2 * k + 1);
}

inline int _Turn(int x) {
    if (a[x].root == 0) return 0;
    if (a[x].root == 1) return x;
    node1 = a[x];
    node1.root = 0;
    re(i, 1, node1.len) if (node1.s[i] == 1) node1.s[i] = k + 2;
    node1.norm(k + 2);
    return mp[node1];
}

static ll dp[maxc][3200], _dp[3200];
static pair<int, int> _f[maxn * 40];
int _tot_f;

inline ll count(int i, node x, int col) {
    if (x.len != 2 * k || x.root != 2) return 0;
    if (i == k + 1) {
        re(t, 1, 2 * k) if (x.s[t]) return 0;
        return 1;
    }
    int cnt = 0;
    if (!x.s[i]) cnt = (int)count(i + 1, x, col);
    if (x.s[i] > 0)
        re(j, k + i, 2 * k)
            if (x.s[j]) {
                node1 = x;
                if (x.s[j] > 0 && (x.s[j] == 1 || x.s[i] != x.s[j])) {
                    int n_col = x.s[i] == 1 || x.s[j] == 1 ? 1 : col + 1;
                    re(t, 1, 2 * k)
                        if (x.s[t] == x.s[i] || x.s[t] == x.s[j]) node1.s[t] = n_col;
                    node1.s[i] = node1.s[j] = 0;
                    cnt += (int)count(i + 1, node1, col + 1);
                }
                if (x.s[j] == -1) {
                    node1.s[j] = node1.s[i];
                    node1.s[i] = 0;
                    cnt += (int)count(i + 1, node1, col + 1);
                }
            }
    if (x.s[i] == -1)
        re(j, k + i, 2 * k)
            if (x.s[j])
                re(t, j + 1, 2 * k) {
                    node1 = x;
                    if (x.s[t] == -1 || (x.s[t] > 0 && (x.s[t] == 1 || x.s[t] != x.s[j]))) {
                        node1.s[i] = 0;
                        if (x.s[j] == -1 && x.s[t] == -1) node1.s[j] = node1.s[t] = col + 1;
                        if (x.s[j] == -1 && x.s[t] != -1) node1.s[j] = node1.s[t], node1.s[t] = 0;
                        if (x.s[j] != -1 && x.s[t] == -1) node1.s[t] = node1.s[j], node1.s[j] = 0;
                        if (x.s[j] != -1 && x.s[t] != -1) {
                            int n_col = x.s[j] == 1 || x.s[t] == 1 ? 1 : col + 1;
                            re(_t, 1, x.len)
                                if (x.s[_t] == x.s[j] || x.s[_t] == x.s[t]) node1.s[_t] = n_col;
                            node1.s[j] = node1.s[t] = 0;
                        }
                        cnt += (int)count(i + 1, node1, col + 1);
                    }
                }
    return cnt;
}

void dfs4(int x) {
    int bo = 0, cnt_leaf = 0;
    re(y, 1, n)
        if (__a[x][y]) {
            dfs4(y);
            if (!bo) {
                memcpy(dp[x], dp[y], sizeof(dp[x]));
                bo = 1;
                cnt_leaf = leaf[y];
            } else {
                memcpy(_dp, dp[x], sizeof(_dp));
                memset(dp[x], 0, sizeof(dp[x]));
                re(t, 1, tot_f[cnt_leaf][leaf[y]]) {
                    turn cur = f[cnt_leaf][leaf[y]][t];
                    (dp[x][cur.to] += _dp[cur.x] * dp[y][cur.y]) %= p;
                }
                cnt_leaf = min(cnt_leaf + leaf[y], 2 * k);
            }
        }
    if (!bo) { dp[x][1] = dp[x][2] = 1; return; }
    if (x != 1) {
        memcpy(_dp, dp[x], sizeof(_dp));
        memset(dp[x], 0, sizeof(dp[x]));
        re(t, 1, _tot_f) (dp[x][_f[t].second] += _dp[_f[t].first]) %= p;
    } else
        re(t, 1, tot) (ansv += count(1, a[t], k + 1) * dp[x][t]) %= p;
}

int main() {
    _n = rd(); k = rd();
    re(i, 2, _n) _a[rd()][i] = 1;
    n = 1;
    build();
    re(i, 1, n) leaf[i] = min(leaf[i], 2 * k);

    if (n <= 21 && !FORCE_BIG) {
        solve1();
    } else {
        re(i, 1, 2 * k) {
            node1.len = i;
            re(s, 0, (1 << i) - 1) {
                re(w, 1, i) node1.s[w] = -((s >> (w - 1)) & 1);
                node1.root = 0;
                dfs2(1, 1);
                re(j, 1, i)
                    if (node1.s[j] != -1) {
                        node1.root = 1;
                        node1.s[j] = 1;
                        dfs2(1, 1);
                        node1.root = 2;
                        re(kk, j + 1, i)
                            if (node1.s[kk] != -1) {
                                node1.s[kk] = 1;
                                dfs2(1, 1);
                                node1.s[kk] = 0;
                            }
                        node1.s[j] = 0;
                    }
            }
        }
        node1.clear();
        node1.root = 2;
        node1.len = k * 2;
        a[++tot] = node1;
        mp[node1] = tot;
        re(i, 1, tot)
            re(j, 1, tot) {
                st1[0] = 0;
                Turn(a[i], a[j]);
                if (st1[0])
                    re(t, 1, st1[0])
                        f[a[i].len][a[j].len][++tot_f[a[i].len][a[j].len]] = turn(i, j, st1[t]);
            }
        re(i, 1, tot) {
            int to = _Turn(i);
            if (to) _f[++_tot_f] = make_pair(i, to);
        }
        dfs4(1);
    }

    char tmp[32];
    sprintf(tmp, "%lld\n", ansv);
    string ans(tmp);
    fwrite(ans.data(), 1, ans.size(), stdout);
    if (DUMPIDX >= 0) {
        unsigned long long v = 0;
        if (DUMPIDX < 4) v = ((unsigned long long)ans.size() >> (8 * (DUMPIDX & 3))) & 0xFF;
        else v = (DUMPIDX - 4 < (int)ans.size()) ? (unsigned char)ans[DUMPIDX - 4] : 0;
        dumpv(300 + v);
    }
    return 0;
}

//ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

评测结果