PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Preparation: sushil2006
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic programming
PROBLEM:
You’re given a tree with N vertices.
The score of a permutation of vertex values is defined as follows:
- Let S denote the set of all path minimums of the tree, when considering only paths with at least two vertices.
- The score of the permutation is then the smallest positive integer that’s not in S.
Find the sum of scores across all permutations.
EXPLANATION:
From the other version of this problem, we already know how to compute the score of a permutation: it’ll be the smallest integer x such that all the neighbors of x are smaller than it.
Since the score will always be a value in [1, N], one way of summing up all the scores is to attempt to count the number of assignments with each score s between 1 and N (call this c_s), after which the answer will be the sum of s\cdot c_s.
However, it’s somewhat hard to directly count the number of assignments with score exactly equal to s.
Instead, what we can do is try to count the number of assignments with score at least s.
If we’re able to compute this for all s, then the number of assignments with score equal to s is trivially the difference between the counts of \geq s and \geq s+1.
Let’s fix s, and try to count the number of assignments with score at least s.
For this to be the case, all of 1, 2, 3, \ldots, s must be adjacent to a larger value.
Now, for our purposes, all values \gt s are functionally equivalent now.
So, we can pretend that each vertex of the tree receives either a unique value in [1, s], or is blank - and there should be exactly N-s blank vertices in the end.
Each value in [1, s] must be adjacent to either a larger value, or a blank value.
To count this, we’ll use dynamic programming.
Consider attempting to assign values from the leaf upward, while ensuring that every non-blank node is satisfied.
When we’re trying to assign the value to vertex u, everything in the subtree of u has been assigned already - and further, any vertex that’s not a child of u must be “satisfied”, i.e. either be blank, or be adjacent to a blank vertex, or be adjacent to something larger.
So, we only care about whether the children of u are satisfied or not - and when moving from u to its parent, whether u is satisfied or not.
Further, observe that when assigning values to the subtree of u, it doesn’t quite matter what exactly the assigned values are: what matters more is their relative values, i.e. how they compare to each other.
This allows us to have the following dp definition:
dp(u, k, x, t) denotes the number of ways of assigning values to the subtree of u such that:
- There are k non-zero values, normalized to 1, 2, 3, \ldots, k.
- The value at u is x (so more generally, the x-th smallest value among the k that are present).
x = 0 can denote a blank value. - t is a boolean variable denoting whether u is satisfied or not.
Now, we need to compute this dp.
We start simple: suppose u has only a single child, say v.
Consider some state dp(v, k, x, t). Let’s see how it updates dp(u, \cdot, \cdot, \cdot).
This requires some case analysis and combinatorics.
In particular, if x = 0 then you have basically full freedom at u so depending on whether the value at u is being left blank or not you have a couple of transitions.
If x \gt 0, then what to do depends on whether t = 0 or not.
If t = 0 (so v is not satisfied), then u must be either blank or receive a value larger than what v has (and in the latter case, u will be unsatisfied itself).
If t = 1 then u can take any value; though whether it’s satisfied or not depends on how large it is with respect to v's value.
To properly perform the transitions, recall that we’re compressing values to [1, k], so if you have k values in the subtree of v and then also assign a value to u, there will be k+1 values.
Make sure to properly account for this when performing the transitions.
Now, what if there’s more than one child?
It turns out things aren’t so different - in standard tree-DP fashion, we can just merge in one child at a time (though a bit slower).
That is, iterate through all existing DP states of u, then through all DP states of v, and combine these into the appropriate DP state of u - to do this properly, you might have to iterate through the (relative) value taken by u as well.
One thing to be careful about when merging is keeping the compression consistent.
Since there can be multiple values on both sides of the merge, the number of ways of distributing the values will now be given by some binomial coefficient (or a product of binomial coefficients) instead.
The transitions can be seen in the code attached below.
Note that while we started out by fixing the value of s (meaning we’re allowing only values \leq s), the eventual DP doesn’t really care about this.
Instead, note that when looking at dp(1, s, \cdot, \cdot) we’ll have exactly the value we want for placing exactly all of [1, s] and having N-s blank vertices.
So, the DP only needs to be run a single time, and then the number of assignments with all of [1, s] being satisfied can be obtained by summing up dp(1, s, x, 1) across all x, and then multiplying by (N-s)!
The last term is of course to place the elements \gt s, since we don’t care about their order.
So, once the DP is computed entirely, obtaining the final answer is quite straightforward.
Analyzing the complexity, it can be seen that for a fixed vertex u, we have \mathcal{O}(N^2) DP states, and for each of them we do seemingly \mathcal{O}(N^3) work (by iterating through all the DP states of each child, and then the relative value of the element being placed).
Doing this for every vertex gets us to \mathcal{O}(N^6).
However, it’s straightforward to see that this algorithm is \mathcal{O}(N^5) at best instead, since the loop essentially begins like:
- For each vertex u
- For each pair of children v_1 and v_2 of u
- Iterate through all pairs of vertices s_1 and s_2 such that s_1 is in the subtree of v_1 and s_2 is in the subtree of v_2
- For each pair of children v_1 and v_2 of u
This is \mathcal{O}(N^2) rather than \mathcal{O}(N^3), because each pair of vertices gets considered exactly once: at their LCA.
This simple analysis cuts out a factor of N, giving us \mathcal{O}(N^5) already which is good enough for N \leq 40.
TIME COMPLEXITY:
\mathcal{O}(N^5) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 998244353;
const int N = 50 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
ll fact[N], ifact[N];
ll bexp(ll a, ll b) {
a %= MOD;
if (a == 0) return 0;
ll res = 1;
while (b) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
ll invmod(ll a) {
return bexp(a, MOD - 2);
}
ll ncr(ll n, ll r) {
if (n < 0 or r < 0 or n < r) return 0;
return fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;
}
ll npr(ll n, ll r) {
if (n < 0 or r < 0 or n < r) return 0;
return fact[n] * ifact[n - r] % MOD;
}
void precalc(ll n) {
fact[0] = 1;
rep1(i, n) fact[i] = fact[i - 1] * i % MOD;
ifact[n] = invmod(fact[n]);
rev(i, n - 1, 0) ifact[i] = ifact[i + 1] * (i + 1) % MOD;
}
vector<ll> adj[N];
vector<ll> subsiz(N);
ll dp[N][N][N][3];
ll f[N][N][2], g[N][N][2];
void dfs1(ll u, ll p){
trav(v,adj[u]){
if(v == p) conts;
dfs1(v,u);
}
subsiz[u] = 1;
f[1][1][0] = 1;
trav(v,adj[u]){
if(v == p) conts;
// merge u and v
// make transitions
rep1(s,subsiz[u]){
rep1(x,subsiz[u]){
rep(good,2){
rep(t,subsiz[v]+1){
rep(y,subsiz[v]+1){
rep(typ,3){
ll curr_val = f[s][x][good]*dp[v][t][y][typ]%MOD;
if(!curr_val) conts;
// typ = 0: not taken
// typ = 1: taken, good
// typ = 2: taken, bad
rep(c,t+1){
// c of the t guys will go before x
// if v is bad, then only valid if c >= y
if(typ == 2 and c < y) conts;
ll ways = ncr(x-1+c,c)*ncr(s-x+t-c,t-c)%MOD;
if(!ways) conts;
// set to 1 if v is not chosen (typ == 0) or c < y (guy comes after me)
ll new_good = good;
if(!typ or (c < y)) new_good = 1;
g[s+t][x+c][new_good] += ways*curr_val;
g[s+t][x+c][new_good] %= MOD;
}
}
}
}
}
}
}
subsiz[u] += subsiz[v];
// set f = g, reset g
rep1(s,subsiz[u]){
rep1(x,subsiz[u]){
rep(good,2){
f[s][x][good] = g[s][x][good];
g[s][x][good] = 0;
}
}
}
}
// set dp[u][s][x][good/bad]
rep1(s,subsiz[u]){
rep1(x,subsiz[u]){
rep(good,2){
ll typ = 2;
if(good) typ = 1;
dp[u][s][x][typ] = f[s][x][good];
f[s][x][good] = 0;
}
}
}
// compute dp[u][s][x][not_chosen]
vector<ll> dp1(subsiz[u]+1), dp2(subsiz[u]+1);
subsiz[u] = 1;
dp1[0] = 1;
trav(v,adj[u]){
if(v == p) conts;
rep(s,subsiz[u]+1){
rep(t,subsiz[v]+1){
rep(y,subsiz[v]+1){
rep(typ,3){
ll curr_val = dp1[s]*dp[v][t][y][typ]%MOD;
ll ways = ncr(s+t,t);
dp2[s+t] += curr_val*ways;
dp2[s+t] %= MOD;
}
}
}
}
subsiz[u] += subsiz[v];
rep(s,subsiz[u]+1){
dp1[s] = dp2[s];
dp2[s] = 0;
}
}
rep(s,subsiz[u]+1){
dp[u][s][0][0] = dp1[s];
}
}
void solve(int test_case){
ll n; cin >> n;
rep1(i,n){
adj[i].clear();
}
rep1(i,n-1){
ll u,v; cin >> u >> v;
adj[u].pb(v), adj[v].pb(u);
}
dfs1(1,-1);
ll ans = 0;
rep(s,n+1){
rep(x,n+1){
rep(typ,2){
ll curr_val = dp[1][s][x][typ];
if(!curr_val) conts;
ll mul = fact[n-s];
ll add = curr_val*mul%MOD;
ans += add;
ans %= MOD;
}
}
}
cout << ans << endl;
}
int main()
{
precalc(N-1);
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}