Write the first few screaming numbers in decimal and see how each one relates to the previous one.

Adding one more digit $$$A$$$ on the right changes the number in a simple way. Can you simulate that directly, keeping everything modulo $$$10^9+7$$$?

Let $$$S_n$$$ be the $$$n$$$-th screaming number, that is, $$$n$$$ copies of the hexadecimal digit $$$A = 10$$$ written in a row, and let $$$S_0 = 0$$$. Appending one more digit $$$A$$$ on the right shifts everything one hexadecimal place to the left (multiplies by $$$16$$$) and adds $$$10$$$:

Check: $$$S_1 = 10$$$, $$$S_2 = 16 \cdot 10 + 10 = 170$$$ and $$$S_3 = 16 \cdot 170 + 10 = 2730$$$, matching the samples.

Start with $$$s = 0$$$ and apply $$$s \leftarrow (16 s + 10) \bmod (10^9+7)$$$ exactly $$$n$$$ times. Print $$$s$$$.

Since $$$s \lt 10^9+7$$$ before each step, $$$16 s + 10$$$ is about $$$1.6 \cdot 10^{10}$$$, which overflows a 32-bit integer, so use long long.

Time: $$$O(n)$$$ per test, memory $$$O(1)$$$.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long

const int MOD = 1e9 + 7;

void solve()
{
    int n = 0;
    cin >> n;
    int s = 0;
    for(int i = 0; i < n; i++)
    {
        s = (s * 16 + 10) % MOD;
    }
    cout << s << '\n';
}

signed main()
{
    auto begin = chrono::high_resolution_clock::now();
    fastio;
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int t = 1;
    cin >> t;
    cout << fixed << setprecision(0);
    while(t--)
    {
        solve();
    }
    auto end = chrono::high_resolution_clock::now();
    auto elapsed = chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Unrolling the recurrence, the digit at position $$$i$$$ (counting from $$$0$$$ on the right) is worth $$$10 \cdot 16^i$$$, so

For $$$n = 2$$$ this gives $$$10 \cdot 255 / 15 = 170$$$, and for $$$n = 3$$$ it gives $$$2730$$$.

The division by $$$15$$$ is exact over the integers, so we can do it modulo $$$p = 10^9+7$$$ with an inverse. $$$p$$$ is prime and does not divide $$$15$$$, so $$$15^{-1} = 15^{p-2} \bmod p$$$ by Fermat's little theorem.

Compute $$$16^n \bmod p$$$ with fast exponentiation (binary exponentiation: square the base at every step and multiply it into the result whenever the current bit of the exponent is set). Subtract $$$1$$$ (add $$$p$$$ first so it never goes negative), then multiply by $$$10$$$ and by $$$15^{-1}$$$, reducing modulo $$$p$$$ after each product.

Time: $$$O(\log n)$$$ per test. This is only needed if $$$n$$$ is too large for a linear loop.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long

const int MOD = 1e9 + 7;

int modexp(int base, int expval)
{
    int res = 1;
    while(expval > 0)
    {
        if(expval & 1LL)
        {
            res = (res * base) % MOD;
        }
        base = (base * base) % MOD;
        expval >>= 1LL;
    }
    return res;
}

void solve()
{
    int n = 0;
    cin >> n;
    cout << (((10 * (modexp(16, n) + MOD - 1)) % MOD) * modexp(15, MOD - 2)) % MOD << '\n';
}

signed main()
{
    auto begin = chrono::high_resolution_clock::now();
    fastio;
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int t = 1;
    cin >> t;
    cout << fixed << setprecision(0);
    while(t--)
    {
        solve();
    }
    auto end = chrono::high_resolution_clock::now();
    auto elapsed = chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Looping over a query's range is too slow. Can you work out, for every point at once, how many beams cover it?

Once you know which points are charge zones, each query is just a range count. Which structure answers that in $$$O(1)$$$?

A beam from $$$L$$$ to $$$R$$$ is a difference update: $$$diff_L$$$ goes up by $$$1$$$ and $$$diff_{R+1}$$$ goes down by $$$1$$$.

The running sum of $$$diff$$$ at $$$x$$$ is the number of beams with $$$L \le x$$$ minus the number with $$$R+1 \le x$$$. That is exactly the number of beams covering $$$x$$$, call it $$$cover_x$$$.

Let $$$zone_x = 1$$$ if $$$cover_x \ge k$$$, and $$$0$$$ otherwise. Let $$$pre_x$$$ be the sum of $$$zone_1, zone_2, \dots, zone_x$$$. A query with endpoints $$$l$$$ and $$$r$$$ has answer $$$pre_r - pre_{l-1}$$$.

Make the arrays slightly larger than the biggest coordinate so that $$$R+1$$$ is always valid. Apply all beams to $$$diff$$$, take the running sum to get $$$cover$$$, build $$$pre$$$ in the same pass, and answer each query as $$$pre_r - pre_{l-1}$$$. Coordinates start at $$$1$$$, so $$$l - 1 \ge 0$$$ is always a valid index.

Time: $$$O(n + q + M)$$$, where $$$M$$$ is the largest coordinate. On sample 1 the charge zones are $$$92, 93, 94, 97$$$, which gives answers $$$3, 3, 0, 4$$$.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long

const int N = 2e5 + 10;

void solve()
{
    int n = 0, k = 0, q = 0;
    cin >> n >> k >> q;

    vector<int> diff(N, 0), pre(N, 0);
    for(int i = 0; i < n; i++)
    {
        int l = 0, r = 0;
        cin >> l >> r;
        diff[l]++;
        diff[r + 1]--;
    }

    int cover = 0;
    for(int x = 1; x < N; x++)
    {
        cover += diff[x];
        pre[x] = pre[x - 1] + (cover >= k);
    }

    while(q--)
    {
        int l = 0, r = 0;
        cin >> l >> r;
        cout << pre[r] - pre[l - 1] << '\n';
    }
}

signed main()
{
    auto begin = chrono::high_resolution_clock::now();
    fastio;
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int t = 1;
    cout << fixed << setprecision(0);
    while(t--)
    {
        solve();
    }
    auto end = chrono::high_resolution_clock::now();
    auto elapsed = chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Run BFS and DFS by hand on a few small graphs from vertex $$$1$$$. Is there a position where the two orders always agree?

That is a necessary condition. Is it also sufficient? Try joining vertex $$$1$$$ to every other vertex.

The order you print the edges in is the adjacency order. That decides which neighbor each search looks at first.

If $$$N \ge 2$$$, vertex $$$1$$$ has a first neighbor $$$f$$$. BFS pushes $$$f$$$ first and DFS walks to $$$f$$$ first, so both orders must have the same second element, $$$B_2 = D_2$$$. If they differ, the answer is $$$-1$$$. For $$$N = 1$$$ there is nothing to check.

Now suppose $$$B_2 = D_2$$$. Connect $$$1$$$ to everything in the order $$$B_2, \dots, B_N$$$. Then BFS produces $$$B$$$ no matter what other edges exist, and those other edges are free to steer the DFS. Use the path $$$D_2, D_3, \dots, D_N$$$.

Print the star edges from $$$1$$$ to $$$B_i$$$ for $$$i = 2, \dots, N$$$ first, then the path edges from $$$D_i$$$ to $$$D_{i+1}$$$ for $$$i = 2, \dots, N-1$$$. That is $$$2N - 3$$$ edges for $$$N \ge 2$$$ and none for $$$N = 1$$$. Any valid graph is accepted, so your output may differ from the sample.

Why it works:

1. The graph is valid. Star edges contain vertex $$$1$$$ and path edges do not, so nothing repeats, and it is connected because $$$1$$$ touches everyone. Also $$$2N - 3 \le N(N-1)/2$$$, since the difference is $$$(N-2)(N-3) \ge 0$$$.

2. BFS pops $$$1$$$ and enqueues $$$B_2, \dots, B_N$$$ in that order, which discovers every vertex.

3. For DFS, the adjacency list of $$$D_i$$$ is $$$1, D_{i-1}, D_{i+1}$$$. DFS first goes from $$$1$$$ to $$$B_2 = D_2$$$. When it first arrives at $$$D_i$$$, the visited set is exactly $$$1, D_2, \dots, D_i$$$. So it skips $$$1$$$ and $$$D_{i-1}$$$ and steps to $$$D_{i+1}$$$. At $$$D_N$$$ it only backtracks.

Time: $$$O(N)$$$.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long

void solve()
{
    int n = 0;
    cin >> n;
    vector<int> bf(n + 1, 0), df(n + 1, 0);

    for(int i = 1; i <= n; i++)
    {
        cin >> bf[i];
    }
    for(int i = 1; i <= n; i++)
    {
        cin >> df[i];
    }

    if(n >= 2 && bf[2] != df[2])
    {
        cout << -1 << '\n';
        return;
    }

    set<pair<int, int>> st;
    vector<pair<int, int>> ans;

    for(int i = 1; i <= n; i++)
    {
        if(bf[i] != 1 && st.find({1, bf[i]}) == st.end())
        {
            ans.push_back({1, bf[i]});
            st.insert({1, bf[i]});
        }
    }

    for(int i = 2; i <= n; i++)
    {
        int val1 = min(df[i], df[i - 1]), val2 = max(df[i], df[i - 1]);
        if(st.find({val1, val2}) == st.end())
        {
            ans.push_back({val1, val2});
            st.insert({val1, val2});
        }
    }

    cout << ans.size() << '\n';
    for(auto [a, b] : ans)
    {
        cout << a << " " << b << '\n';
    }
}

signed main()
{
    auto begin = chrono::high_resolution_clock::now();
    fastio;
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int t = 1;
    cin >> t;
    cout << fixed << setprecision(0);
    while(t--)
    {
        solve();
    }
    auto end = chrono::high_resolution_clock::now();
    auto elapsed = chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Each pile is an independent game under normal play. Which theory tells you who wins a sum of games?

Brute-force the Grundy values for small piles and group them by the highest set bit of the pile size. Look at each group as a whole.

For $$$n = 2^k + r$$$ with $$$0 \le r \lt 2^k$$$, you can remove between $$$1$$$ and $$$2^k - 1$$$ stones. Write down which pile sizes you can reach.

By Sprague-Grundy, Sankha wins if and only if the XOR of the Grundy values of all piles is non-zero. The whole problem is computing $$$g(n)$$$ fast.

Write $$$n = 2^k + r$$$ with $$$0 \le r \lt 2^k$$$. The reachable sizes are exactly the $$$m$$$ with $$$r \lt m \lt n$$$. A pile of $$$1$$$ has no moves, so $$$g(1) = 0$$$. Brute force gives

Call the sizes with highest bit $$$2^k$$$ block $$$k$$$. Each block is a permutation of the values $$$0$$$ to $$$2^k - 1$$$, and the pattern is:

1. If $$$r \lt 2^{k-1}$$$, then $$$g(n) = 2^{k-1} + r$$$.
2. If $$$r \ge 2^{k-1}$$$, then $$$g(n) = g(r)$$$.

Induct on $$$k$$$, claiming the formula and that $$$g$$$ maps block $$$k$$$ one-to-one onto the values $$$0$$$ to $$$2^k - 1$$$. Block $$$0$$$ is the single pile $$$1$$$ with value $$$0$$$. Take $$$k \ge 1$$$. By induction every size below $$$2^k$$$ has Grundy value below $$$2^{k-1}$$$.

Case $$$r \lt 2^{k-1}$$$. The reachable sizes include all of block $$$k-1$$$, so every value from $$$0$$$ to $$$2^{k-1} - 1$$$ is reachable. They also include $$$2^k + s$$$ for $$$s \lt r$$$, which by induction on $$$n$$$ have values $$$2^{k-1} + s$$$, so the values $$$2^{k-1}$$$ up to $$$2^{k-1} + r - 1$$$ are reachable. Nothing else is reachable, so the mex is $$$2^{k-1} + r$$$.

Case $$$r \ge 2^{k-1}$$$. The sizes $$$2^k + s$$$ with $$$s \lt 2^{k-1}$$$ are reachable and give every value from $$$2^{k-1}$$$ to $$$2^k - 1$$$. The small values come from two places: sizes $$$p$$$ with $$$r \lt p \lt 2^k$$$ (value $$$g(p)$$$), and sizes $$$2^k + s$$$ with $$$2^{k-1} \le s \lt r$$$ (value $$$g(s)$$$). Together these are the values of everything in block $$$k-1$$$ except $$$r$$$. By the one-to-one property that is every small value except $$$g(r)$$$, so the mex is $$$g(r)$$$.

For the one-to-one property: the first case sends $$$r \lt 2^{k-1}$$$ onto the values $$$2^{k-1}$$$ to $$$2^k - 1$$$, and the second sends block $$$k-1$$$ onto the values $$$0$$$ to $$$2^{k-1} - 1$$$. $$$\blacksquare$$$

To compute $$$g(a)$$$, loop while $$$n \gt 1$$$: find the highest bit $$$2^k$$$ and set $$$r = n - 2^k$$$. If $$$r \lt 2^{k-1}$$$, return $$$2^{k-1} + r$$$, otherwise set $$$n = r$$$ and continue. The bit length drops each step, so this is about $$$30$$$ iterations. If you reach $$$n = 1$$$, return $$$0$$$.

XOR all the values. Print Sankha if the result is non-zero, otherwise Pink Flo. Time: $$$O(N \log A)$$$ per test.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long

int grundy(int n)
{
    while(n > 1)
    {
        int k = 63 - __builtin_clzll(n);
        int r = n - (1LL << k);
        if(r < (1LL << (k - 1)))
        {
            return (1LL << (k - 1)) + r;
        }
        n = r;
    }
    return 0;
}

void solve()
{
    int n = 0;
    cin >> n;
    int x = 0;
    for(int i = 0; i < n; i++)
    {
        int a = 0;
        cin >> a;
        x ^= grundy(a);
    }
    cout << (x ? "Sankha" : "Pink Flo") << '\n';
}

signed main()
{
    auto begin = chrono::high_resolution_clock::now();
    fastio;
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int t = 1;
    cin >> t;
    cout << fixed << setprecision(0);
    while(t--)
    {
        solve();
    }
    auto end = chrono::high_resolution_clock::now();
    auto elapsed = chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

"Strictly increasing" is annoying to handle. Is there a shift by the index that turns it into "non-decreasing" without changing the cost?

After the shift you want the non-decreasing sequence that is closest to the shifted array. Which values do you need to consider for the new elements?

Try a dp over (prefix length, last value). The transition takes the best over all smaller or equal previous values, and that can be a running minimum.

Let $$$c_i = a_i - i$$$ and $$$x_i = b_i - i$$$. Since $$$b_{i+1} \ge b_i + 1$$$ is the same as $$$x_{i+1} \ge x_i$$$, the sequence $$$b$$$ is strictly increasing exactly when $$$x$$$ is non-decreasing. The cost does not change:

Values are allowed to be zero or negative, so $$$x_i$$$ has no lower bound.

Some optimal $$$x$$$ uses only values that already appear among $$$c_1, \dots, c_n$$$. Take an optimal $$$x$$$ and a maximal block of equal values $$$v$$$ where $$$v$$$ is not any $$$c_i$$$. The cost of the block is linear in $$$v$$$ around $$$v$$$ (its breakpoints are the $$$c_i$$$), so $$$v$$$ can move in one direction without raising the cost. It keeps moving until it hits some $$$c_i$$$ or the value of a neighboring block, in which case the two blocks merge. Each move either lands a block on some $$$c_i$$$ or reduces the number of blocks, so the process ends.

Let $$$v_1 \lt v_2 \lt \dots \lt v_m$$$ be the distinct values of $$$c$$$. Let $$$dp_{i,j}$$$ be the minimum cost of the first $$$i$$$ elements when $$$x_i = v_j$$$. Then

The inner minimum enforces $$$x_{i-1} \le x_i$$$. Keep a single row. For each $$$i$$$, sweep $$$j$$$ upwards while maintaining the running minimum of the old row, and overwrite $$$dp_j$$$ with it plus $$$|c_i - v_j|$$$. The answer is the smallest entry of the final row.

Time: $$$O(n^2)$$$, memory $$$O(n)$$$. The answer needs long long. Sample 1 gives $$$9$$$ and sample 2 gives $$$12$$$.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long

void solve()
{
    int n = 0;
    cin >> n;
    vector<int> c(n);
    for(int i = 0; i < n; i++)
    {
        int a = 0;
        cin >> a;
        c[i] = a - i;
    }

    vector<int> v = c;
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    int m = v.size();

    vector<int> dp(m, 0);
    for(int i = 0; i < n; i++)
    {
        int best = LLONG_MAX;
        for(int j = 0; j < m; j++)
        {
            best = min(best, dp[j]);
            dp[j] = best + llabs(c[i] - v[j]);
        }
    }
    cout << *min_element(dp.begin(), dp.end()) << '\n';
}

signed main()
{
    auto begin = chrono::high_resolution_clock::now();
    fastio;
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int t = 1;
    cin >> t;
    cout << fixed << setprecision(0);
    while(t--)
    {
        solve();
    }
    auto end = chrono::high_resolution_clock::now();
    auto elapsed = chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Forget the order of the operations. Which trees can you reach using exactly $$$m$$$ "remove an edge, add an edge" operations?

Suppose the final tree has height at most $$$h$$$ and center $$$c$$$. After you delete the removed edges, how should each leftover piece be attached to $$$c$$$, and how big may it be?

Root the tree at $$$c$$$. The branches hanging off $$$c$$$ do not interact, so each one can be solved on its own.

To cut a rooted tree into the fewest pieces of bounded diameter, go bottom-up. At a vertex, which child branches do you cut first?

You need this cost for every possible center, which is rerooting. And feasibility is monotone in $$$h$$$.

1. The height of a tree is its radius, which is $$$\lceil d / 2 \rceil$$$ where $$$d$$$ is the diameter, and a center can be taken to be a vertex.
2. Only the set $$$R$$$ of original edges that are missing from the final tree matters. The final tree contains the forest $$$T - R$$$ and joins its pieces.
3. A piece not containing the center is best joined to $$$c$$$ through its own center. Its depth from $$$c$$$ is then $$$1$$$ plus its radius.

So we binary search on $$$h$$$. For a fixed $$$h$$$, let $$$D = 2h - 2$$$ and find the cheapest way to cut things when each vertex is tried as the center.

Lemma 1. A tree $$$T'$$$ is reachable from $$$T$$$ in at most $$$k$$$ operations if and only if at most $$$k$$$ edges of $$$T$$$ are missing from $$$T'$$$.

($$$\Rightarrow$$$) Each operation adds one new edge, so the number of missing original edges grows by at most $$$1$$$.

($$$\Leftarrow$$$) Induct on the number of missing edges. Pick a missing edge $$$e$$$. $$$T'$$$ is connected and does not contain $$$e$$$, so it has some edge $$$f$$$ joining the two sides of $$$T - e$$$. That $$$f$$$ is not in $$$T$$$ (since $$$e$$$ was the only edge of $$$T$$$ across), so $$$T - e + f$$$ is one operation away and is closer to $$$T'$$$. $$$\blacksquare$$$

Lemma 2. For $$$h \ge 1$$$, height at most $$$h$$$ is reachable in at most $$$k$$$ operations if and only if there are a set $$$R$$$ of at most $$$k$$$ edges and a vertex $$$c$$$ such that in $$$T - R$$$:

1. every vertex of $$$c$$$'s component is within distance $$$h$$$ of $$$c$$$, and
2. every other component has diameter at most $$$D = 2h - 2$$$.

($$$\Leftarrow$$$) Join the center of each other component to $$$c$$$. Such a component has radius at most $$$h - 1$$$, so all its vertices are within $$$h$$$ of $$$c$$$. $$$T - R$$$ has $$$|R| + 1$$$ components, so $$$|R|$$$ new edges make a tree. Apply Lemma 1.

($$$\Rightarrow$$$) Let $$$T'$$$ be reachable with a vertex $$$c$$$ of eccentricity at most $$$h$$$, and let $$$R$$$ be the original edges missing from $$$T'$$$. Every component of $$$T - R$$$ is a subtree of $$$T'$$$. For $$$c$$$'s own component the path from $$$c$$$ in $$$T'$$$ stays inside it, which gives condition 1. For another component $$$C$$$, there is a unique vertex $$$x$$$ of $$$C$$$ closest to $$$c$$$, and every path from $$$c$$$ into $$$C$$$ goes through $$$x$$$. So $$$h \ge 1 + d_C(x, y)$$$ for every $$$y$$$ in $$$C$$$, where $$$d_C$$$ is the distance inside $$$C$$$. Hence $$$x$$$ has eccentricity at most $$$h - 1$$$ in $$$C$$$, and the diameter of $$$C$$$ is at most $$$2h - 2$$$. $$$\blacksquare$$$

Let $$$cost_h(c)$$$ be the smallest $$$|R|$$$ satisfying both conditions. Height at most $$$h$$$ is feasible exactly when some $$$c$$$ has $$$cost_h(c) \le k$$$. Larger $$$h$$$ only helps ($$$h = n$$$ works with $$$R$$$ empty), so we can binary search.

Lemma 3. Root $$$T$$$ at $$$c$$$. For a neighbor $$$w$$$ of $$$c$$$, call a set of edges inside the subtree of $$$w$$$ a D-partition if removing it leaves pieces of diameter at most $$$D$$$. Among all D-partitions, let $$$(g_w, d_w)$$$ be the lexicographically smallest pair of (number of edges removed, depth of $$$w$$$'s piece measured from $$$w$$$). Then $$$cost_h(c)$$$ is the sum over neighbors $$$w$$$ of $$$g_w$$$, plus one more for each $$$w$$$ with $$$d_w \ge h$$$.

Why. Branches are independent. If the edge from $$$c$$$ to $$$w$$$ is removed, the whole branch must be D-partitioned, which costs at least $$$g_w + 1$$$. If it is kept, $$$w$$$'s piece needs depth at most $$$h - 1$$$ from $$$w$$$, which also implies diameter at most $$$D$$$. So the cuts form a D-partition, which costs at least $$$g_w$$$, and $$$g_w$$$ is achievable exactly when $$$d_w \le h - 1$$$. Otherwise keeping the edge costs at least $$$g_w + 1$$$, no better than cutting it. $$$\blacksquare$$$

Lemma 4 (greedy). Let $$$v$$$ have children with pairs $$$(g_i, d_i)$$$ and put $$$a_i = d_i + 1$$$, the depth of child $$$i$$$'s piece measured from $$$v$$$. Sort $$$a$$$ in decreasing order as $$$a_{(1)} \ge a_{(2)} \ge \dots$$$ and pad with zeros. Let $$$t$$$ be the smallest $$$t \ge 0$$$ with $$$a_{(t+1)} + a_{(t+2)} \le D$$$. Then

Achievable. Cut the edges to the $$$t$$$ children with the largest $$$a$$$ and use each child's own optimal partition. The longest path through $$$v$$$ then has length $$$a_{(t+1)} + a_{(t+2)} \le D$$$, and the depth of $$$v$$$'s piece is $$$a_{(t+1)}$$$.

Optimal. Take any D-partition of the subtree of $$$v$$$. Inside child $$$u$$$ it has at least $$$g_u$$$ cuts. If the edge to $$$u$$$ is kept but the branch uses more than $$$g_u$$$ cuts, swap in an optimal branch for $$$u$$$ and cut the edge to $$$u$$$ as well. This does not raise the number of cuts and only shrinks $$$v$$$'s piece. If the edge is kept with exactly $$$g_u$$$ cuts, use the branch with the smallest depth. If the edge is cut, an optimal branch is at least as good. So we may assume every branch is optimal and only the child edges to cut remain to be chosen. A set of kept children is valid exactly when the two largest kept values sum to at most $$$D$$$, and cutting the largest values leaves the pointwise smallest list. So at least $$$t$$$ cuts are needed, and with exactly $$$t$$$ cuts the depth is at least $$$a_{(t+1)}$$$. $$$\blacksquare$$$

Example. A path of $$$6$$$ vertices rooted at one end, with $$$D = 2$$$. Going up from the leaf the depths are $$$0, 1, 2$$$. The next vertex would have $$$a = 3$$$, which is more than $$$2$$$, so we cut once and the depth resets to $$$0$$$. Then $$$1, 2$$$ again. At the root $$$g = 1$$$ and $$$d = 2$$$, which is two pieces of $$$3$$$ vertices.

Binary search $$$h$$$ from $$$1$$$ to $$$n$$$ with $$$D = 2h - 2$$$. To test one $$$h$$$:

1. Down pass (reverse BFS order from vertex $$$1$$$): for each vertex compute the pair $$$(g, d)$$$ of its subtree using Lemma 4. Sort the children's values in decreasing order and find $$$t$$$ by binary search on the sorted list.

2. Up pass (BFS order): for each vertex $$$v$$$, collect the pairs of all neighbors, using the down pair for children and the stored up pair for the parent. The cost of $$$v$$$ as the center is given by Lemma 3. If it is at most $$$k$$$, then $$$h$$$ is feasible.

3. Otherwise, for each child $$$u$$$ of $$$v$$$, compute $$$u$$$'s up pair by applying Lemma 4 to $$$v$$$'s neighbor list with $$$u$$$ removed. You do not need to rebuild the list: use the sorted array while skipping $$$u$$$'s position (a virtual array), and binary search for $$$t$$$ on it. Store each sorted entry as ((d + 1) << 20) | id to know which neighbor it belongs to. This is safe because $$$n$$$ is below $$$2^{20}$$$, and ties between equal depths do not matter.

One test of $$$h$$$ costs $$$O(n \log n)$$$, so the total is $$$O(n \log^2 n)$$$ time and $$$O(n)$$$ memory. A path of $$$7$$$ vertices with $$$k = 0$$$ gives $$$3$$$. With $$$k = 1$$$, center $$$3$$$ and the edge between $$$5$$$ and $$$6$$$ cut, it gives $$$2$$$. A single edge gives $$$1$$$.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long

int n, K;
vector<int> st, adjv, order_, par_;
vector<int> dg, dd, ug, ud;

bool feasible(int h)
{
    int D = 2 * h - 2;
    vector<int> buf, a;

    // down pass: (g, d) of every subtree
    for(int idx = n - 1; idx >= 0; idx--)
    {
        int v = order_[idx];
        a.clear();
        int sg = 0;
        for(int e = st[v]; e < st[v + 1]; e++)
        {
            int u = adjv[e];
            if(u == par_[v]) continue;
            a.push_back(dd[u] + 1);
            sg += dg[u];
        }
        sort(a.begin(), a.end(), greater<int>());
        int m = a.size();
        auto b = [&](int i) { return i < m ? a[i] : 0LL; };
        int lo = 0, hi = m;
        while(lo < hi)
        {
            int mid = (lo + hi) / 2;
            if(b(mid) + b(mid + 1) <= D) hi = mid; else lo = mid + 1;
        }
        dg[v] = sg + lo;
        dd[v] = lo < m ? a[lo] : 0;
    }

    // up pass: try every vertex as the center, push (g, d) down to the children
    for(int idx = 0; idx < n; idx++)
    {
        int v = order_[idx];
        buf.clear();
        int sg = 0;
        for(int e = st[v]; e < st[v + 1]; e++)
        {
            int u = adjv[e];
            int g, d;
            if(u == par_[v]) { g = ug[v]; d = ud[v]; }
            else { g = dg[u]; d = dd[u]; }
            sg += g;
            buf.push_back(((d + 1) << 20) | u);
        }
        sort(buf.begin(), buf.end(), greater<int>());
        int m = buf.size();
        a.assign(m, 0);
        int cnt = 0;
        for(int i = 0; i < m; i++)
        {
            a[i] = buf[i] >> 20;
            if(a[i] > h) cnt++;
        }
        if(sg + cnt <= K) return true;
        for(int q = 0; q < m; q++)
        {
            int u = buf[q] & ((1LL << 20) - 1);
            if(u == par_[v]) continue;
            int len = m - 1;
            auto b = [&](int i) { return i < len ? (i < q ? a[i] : a[i + 1]) : 0LL; };
            int lo = 0, hi = len;
            while(lo < hi)
            {
                int mid = (lo + hi) / 2;
                if(b(mid) + b(mid + 1) <= D) hi = mid; else lo = mid + 1;
            }
            ug[u] = sg - dg[u] + lo;
            ud[u] = lo < len ? b(lo) : 0;
        }
    }
    return false;
}

void solve()
{
    cin >> n >> K;
    vector<int> eu(n - 1), ev(n - 1);
    st.assign(n + 2, 0);
    for(int i = 0; i < n - 1; i++)
    {
        cin >> eu[i] >> ev[i];
        eu[i]--; ev[i]--;
        st[eu[i] + 1]++; st[ev[i] + 1]++;
    }
    for(int i = 0; i < n; i++) st[i + 1] += st[i];

    adjv.assign(2 * (n - 1), 0);
    vector<int> pos(st.begin(), st.begin() + n);
    for(int i = 0; i < n - 1; i++)
    {
        adjv[pos[eu[i]]++] = ev[i];
        adjv[pos[ev[i]]++] = eu[i];
    }

    order_.clear();
    par_.assign(n, -1);
    order_.push_back(0);
    for(int i = 0; i < (int)order_.size(); i++)
    {
        int v = order_[i];
        for(int e = st[v]; e < st[v + 1]; e++)
        {
            int u = adjv[e];
            if(u != par_[v]) { par_[u] = v; order_.push_back(u); }
        }
    }

    dg.assign(n, 0); dd.assign(n, 0); ug.assign(n, 0); ud.assign(n, 0);
    int lo = 1, hi = n;
    while(lo < hi)
    {
        int mid = (lo + hi) / 2;
        if(feasible(mid)) hi = mid; else lo = mid + 1;
    }
    cout << lo << '\n';
}

signed main()
{
    auto begin = chrono::high_resolution_clock::now();
    fastio;
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int t = 1;
    cin >> t;
    cout << fixed << setprecision(0);
    while(t--)
    {
        solve();
    }
    auto end = chrono::high_resolution_clock::now();
    auto elapsed = chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Use the same shift $$$c_i = a_i - i$$$ as in the easy version. You want the closest non-decreasing integer sequence.

Let $$$G_i(X)$$$ be the minimum cost of the first $$$i$$$ elements when the last value is at most $$$X$$$. Draw it for the first few $$$i$$$. What shape is it?

$$$G_i$$$ is convex and non-increasing, so it is determined by where its slope changes. Work out how adding element $$$i+1$$$ changes those points.

Only the rightmost slope-change point ever gets touched. Which data structure supports that?

Define $$$G_0(X) = 0$$$ and

The answer is the final constant value of $$$G_n$$$. Each $$$G_i$$$ is convex and non-increasing, so it can be written as a constant $$$m_i$$$ plus one "hinge" per element of a multiset $$$P_i$$$ of $$$i$$$ integers:

The claim is that $$$P_i$$$ is exactly the max-heap of the algorithm below after step $$$i$$$, and $$$m_i$$$ is the running answer.

Induct on $$$i$$$, with $$$P_0$$$ empty and $$$m_0 = 0$$$. Let $$$Q$$$ be $$$P_{i-1}$$$ with $$$c_i$$$ added, and let $$$top$$$ be the maximum of $$$Q$$$. Using $$$|c - Y| = \max(0, c - Y) + \max(0, Y - c)$$$, the function $$$H(Y) = G_{i-1}(Y) + |c_i - Y|$$$ equals

Let $$$s(Y)$$$ be the number of elements of $$$Q$$$ that are larger than $$$Y$$$. The slope of $$$H$$$ at $$$Y$$$ is $$$-s(Y)$$$, plus $$$1$$$ once $$$Y \ge c_i$$$. $$$G_i$$$ is the prefix minimum of $$$H$$$.

Case $$$c_i = top$$$. The slope is at most $$$-1$$$ before $$$c_i$$$ and $$$+1$$$ from $$$c_i$$$ on, so the minimum is at $$$c_i$$$. $$$G_i$$$ follows $$$H$$$ up to $$$c_i$$$ and is constant after. Up to $$$c_i$$$ the last term of $$$H$$$ is $$$0$$$, so $$$G_i(X) = m_{i-1} + \sum_{p \in Q} \max(0, p - X)$$$ for all $$$X$$$. That means $$$P_i = Q$$$ and $$$m_i = m_{i-1}$$$.

Case $$$c_i \lt top$$$. For $$$Y \ge top$$$ the slope is $$$+1$$$. For $$$Y \lt top$$$ at least one element of $$$Q$$$ is above $$$Y$$$, so the slope is at most $$$0$$$. So $$$G_i$$$ equals $$$H$$$ for $$$X \le top$$$ and is constant after. For $$$X \le top$$$ we have $$$\max(0, top - X) = top - X$$$ and $$$\max(0, X - c_i) = \max(0, c_i - X) + X - c_i$$$. Substituting, the terms $$$-X$$$ and $$$+X$$$ cancel and

where $$$Q'$$$ is $$$Q$$$ with one copy of $$$top$$$ replaced by $$$c_i$$$. All elements of $$$Q'$$$ are at most $$$top$$$, so the sum is $$$0$$$ for $$$X \ge top$$$ and the formula also covers the constant part. Hence $$$m_i = m_{i-1} + (top - c_i)$$$ and $$$P_i = Q'$$$.

Both cases are exactly what the algorithm does, and the answer is $$$m_n$$$. $$$\blacksquare$$$

Keep an answer $$$ans = 0$$$ and a max-heap. For each $$$i$$$, push $$$c_i = a_i - i$$$. If the top of the heap is larger than $$$c_i$$$, add $$$top - c_i$$$ to $$$ans$$$, pop the top and push $$$c_i$$$ again. Print $$$ans$$$.

Use long long (the answer can reach about $$$2 \cdot 10^{14}$$$) and reset the heap for every test. Time: $$$O(n \log n)$$$.

Sample 1: $$$c = 2, 0, 3, 8, 1, 4, 5$$$. Adding $$$0$$$ costs $$$2$$$ and adding $$$1$$$ costs $$$7$$$, total $$$9$$$. Sample 2: $$$c = 5, 3, 1, -1, -3$$$ costs $$$2, 2, 4, 4$$$, total $$$12$$$.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long

void solve()
{
    int n = 0;
    cin >> n;
    priority_queue<int> pq;
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        int a = 0;
        cin >> a;
        int x = a - i;
        pq.push(x);
        if(pq.top() > x)
        {
            ans += pq.top() - x;
            pq.pop();
            pq.push(x);
        }
    }
    cout << ans << '\n';
}

signed main()
{
    auto begin = chrono::high_resolution_clock::now();
    fastio;
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int t = 1;
    cin >> t;
    cout << fixed << setprecision(0);
    while(t--)
    {
        solve();
    }
    auto end = chrono::high_resolution_clock::now();
    auto elapsed = chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}