Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Ignore the distance condition at first. The “choose the available vertex with maximum depth” rule forces a recursive traversal: after entering a child subtree, you cannot return to its siblings until that subtree is finished.
So every valid no-distance order is exactly a DFS preorder where each vertex independently chooses a permutation of its children. The only freedom is the child order at every vertex.
Most adjacent pairs in this DFS order are harmless. Parent to first child has distance . The only dangerous jump is from the last vertex of one child subtree to the root of the next sibling subtree.
If child of is followed by sibling , and the walk inside ends edges below , then the jump length is . Therefore a non-last child subtree must end with .
Let count valid walks of subtree ending edges below . For each vertex, choose which child is last; every other child contributes only its prefix sum . Use small-to-large deques with lazy scaling so long chains don't turn your solution into quadratic soup.
The traversal is secretly DFS
The parent rule says a vertex becomes available only after its parent is placed. The depth rule says that among all available vertices, we must pick one with maximum depth.
Suppose we place a child of some vertex . If still has unvisited descendants, the next available vertices inside 's subtree are deeper than all still-waiting siblings of . So we are forced to keep working inside 's subtree until it is completely done.
Therefore every legal order, before checking distances, is exactly this:
So the only choices are the child permutations at each vertex. The scary priority rule was just DFS in a trench coat.
Where distance matters
Inside a child subtree, constraints are handled recursively.
For a vertex , the jump from to its first child has distance , so it is always fine because .
The only jump that can fail is between two consecutive child subtrees of the same vertex :
where is the final vertex produced by one child subtree rooted at , and is the next child of .
If is edges below , then
So a child subtree that is not last among its siblings must end with
The last child has no outgoing sibling jump, so it has no such restriction.
DP
For every vertex , define
For a leaf:
For an internal vertex with children , define
This is the number of ways to process child when it is not the last child of .
Now choose the last child. If is last, all other children must be good, and they can appear in any order, giving permutations. Therefore
Use prefix and suffix products of the values to compute
without division. Some values can be zero, and modular division by zero is, scientifically speaking, a bad time.
The answer is
because the root's final vertex has no later jump to satisfy.
Making it fast
A plain vector DP can go quadratic on a path: each parent would copy and shift a longer and longer array. Nope.
Store each as a deque. Shifting depths by is just push_front(0), so a long chain costs linear time.
We also need whole-array multiplication by coefficients. Doing that eagerly is another quadratic trap, so each deque has a lazy multiplier mul; the actual value at index is
For each deque we maintain:
total: sum of all actual entries;good: sum of actual entries with index .Then good(child) is .
When shifting by one, total does not change. The new good loses exactly the old value at index :
For merging children at a vertex, choose the contributing child with the largest deque as the base. Scale it lazily by its coefficient, then add every smaller child into it. This is the small-to-large part; total explicit element additions are , and all degree/product work is linear.
Processing vertices from down to works because every parent index is smaller than its child index.
Complexity: per total input size, with memory.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int addmod(int a, int b) {
int s = a + b;
if (s >= MOD) s -= MOD;
return s;
}
int submod(int a, int b) {
int s = a - b;
if (s < 0) s += MOD;
return s;
}
int mulmod(ll a, ll b) {
return int(a * b % MOD);
}
int modpow(int a, int e = MOD - 2) {
int r = 1;
while (e) {
if (e & 1) r = mulmod(r, a);
a = mulmod(a, a);
e >>= 1;
}
return r;
}
struct Bag {
deque<int> a;
int mul = 1;
int good = 0;
int total = 0;
};
int actual_at(const Bag *b, int i) {
if (i < 0 || i >= (int)b->a.size()) return 0;
return mulmod(b->a[i], b->mul);
}
void scale_bag(Bag *b, int c) {
if (c == 1) return;
b->mul = mulmod(b->mul, c);
b->good = mulmod(b->good, c);
b->total = mulmod(b->total, c);
}
void merge_into(Bag *to, Bag *from, int coef) {
if (coef == 0 || from->a.empty()) return;
if (to->a.size() < from->a.size()) to->a.resize(from->a.size(), 0);
int factor = mulmod(mulmod(coef, from->mul), modpow(to->mul));
for (int i = 0; i < (int)from->a.size(); i++) {
to->a[i] = addmod(to->a[i], mulmod(factor, from->a[i]));
}
to->good = addmod(to->good, mulmod(coef, from->good));
to->total = addmod(to->total, mulmod(coef, from->total));
}
void shift_bag(Bag *b, int border) {
if (b->a.empty()) return;
if (border >= 0) b->good = submod(b->good, actual_at(b, border));
else b->good = 0;
b->a.push_front(0);
}
int main() {
setIO();
int T;
cin >> T;
const int MAXN = 300000;
vector<int> fact(MAXN + 1, 1);
for (int i = 1; i <= MAXN; i++) fact[i] = mulmod(fact[i - 1], i);
while (T--) {
int n, k;
cin >> n >> k;
vector<vector<int>> child(n + 1);
for (int v = 2; v <= n; v++) {
int p;
cin >> p;
child[p].push_back(v);
}
int border = k - 2;
vector<Bag*> dp(n + 1, nullptr);
for (int v = n; v >= 1; v--) {
int m = (int)child[v].size();
if (m == 0) {
Bag *b = new Bag();
b->a.push_back(1);
b->total = 1;
b->good = (border >= 0 ? 1 : 0);
dp[v] = b;
continue;
}
vector<int> good(m), pref(m + 1, 1), suff(m + 1, 1), coef(m);
for (int i = 0; i < m; i++) good[i] = dp[child[v][i]]->good;
for (int i = 0; i < m; i++) pref[i + 1] = mulmod(pref[i], good[i]);
for (int i = m - 1; i >= 0; i--) suff[i] = mulmod(suff[i + 1], good[i]);
int orderWays = fact[m - 1];
int base = -1;
for (int i = 0; i < m; i++) {
coef[i] = mulmod(orderWays, mulmod(pref[i], suff[i + 1]));
Bag *cur = dp[child[v][i]];
if (coef[i] != 0 && !cur->a.empty()) {
if (base == -1 || cur->a.size() > dp[child[v][base]]->a.size()) base = i;
}
}
if (base == -1) {
for (int u : child[v]) delete dp[u];
dp[v] = new Bag();
continue;
}
Bag *res = dp[child[v][base]];
scale_bag(res, coef[base]);
for (int i = 0; i < m; i++) {
if (i == base) continue;
merge_into(res, dp[child[v][i]], coef[i]);
delete dp[child[v][i]];
}
shift_bag(res, border);
dp[v] = res;
}
cout << dp[1]->total << '\n';
delete dp[1];
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int addmod(int a, int b) {
int s = a + b;
if (s >= MOD) s -= MOD;
return s;
}
int submod(int a, int b) {
int s = a - b;
if (s < 0) s += MOD;
return s;
}
int mulmod(ll a, ll b) {
return int(a * b % MOD);
}
int modpow(int a, int e = MOD - 2) {
int r = 1;
while (e) {
if (e & 1) r = mulmod(r, a);
a = mulmod(a, a);
e >>= 1;
}
return r;
}
struct Bag {
deque<int> a;
int mul = 1;
int good = 0;
int total = 0;
};
int actual_at(const Bag *b, int i) {
if (i < 0 || i >= (int)b->a.size()) return 0;
return mulmod(b->a[i], b->mul);
}
void scale_bag(Bag *b, int c) {
if (c == 1) return;
b->mul = mulmod(b->mul, c);
b->good = mulmod(b->good, c);
b->total = mulmod(b->total, c);
}
void merge_into(Bag *to, Bag *from, int coef) {
if (coef == 0 || from->a.empty()) return;
if (to->a.size() < from->a.size()) to->a.resize(from->a.size(), 0);
int factor = mulmod(mulmod(coef, from->mul), modpow(to->mul));
for (int i = 0; i < (int)from->a.size(); i++) {
to->a[i] = addmod(to->a[i], mulmod(factor, from->a[i]));
}
to->good = addmod(to->good, mulmod(coef, from->good));
to->total = addmod(to->total, mulmod(coef, from->total));
}
void shift_bag(Bag *b, int border) {
if (b->a.empty()) return;
if (border >= 0) b->good = submod(b->good, actual_at(b, border));
else b->good = 0;
b->a.push_front(0);
}
int main() {
setIO();
int T;
cin >> T;
const int MAXN = 300000;
vector<int> fact(MAXN + 1, 1);
for (int i = 1; i <= MAXN; i++) fact[i] = mulmod(fact[i - 1], i);
while (T--) {
int n, k;
cin >> n >> k;
vector<vector<int>> child(n + 1);
for (int v = 2; v <= n; v++) {
int p;
cin >> p;
child[p].push_back(v);
}
int border = k - 2;
vector<Bag*> dp(n + 1, nullptr);
for (int v = n; v >= 1; v--) {
int m = (int)child[v].size();
if (m == 0) {
Bag *b = new Bag();
b->a.push_back(1);
b->total = 1;
b->good = (border >= 0 ? 1 : 0);
dp[v] = b;
continue;
}
vector<int> good(m), pref(m + 1, 1), suff(m + 1, 1), coef(m);
for (int i = 0; i < m; i++) good[i] = dp[child[v][i]]->good;
for (int i = 0; i < m; i++) pref[i + 1] = mulmod(pref[i], good[i]);
for (int i = m - 1; i >= 0; i--) suff[i] = mulmod(suff[i + 1], good[i]);
int orderWays = fact[m - 1];
int base = -1;
for (int i = 0; i < m; i++) {
coef[i] = mulmod(orderWays, mulmod(pref[i], suff[i + 1]));
Bag *cur = dp[child[v][i]];
if (coef[i] != 0 && !cur->a.empty()) {
if (base == -1 || cur->a.size() > dp[child[v][base]]->a.size()) base = i;
}
}
if (base == -1) {
for (int u : child[v]) delete dp[u];
dp[v] = new Bag();
continue;
}
Bag *res = dp[child[v][base]];
scale_bag(res, coef[base]);
for (int i = 0; i < m; i++) {
if (i == base) continue;
merge_into(res, dp[child[v][i]], coef[i]);
delete dp[child[v][i]];
}
shift_bag(res, border);
dp[v] = res;
}
cout << dp[1]->total << '\n';
delete dp[1];
}
return 0;
}