Only administrators can do this, not me.

I dont know about the formulas, but you should use long long instead of int.

Bro your code won't return any output if k is equal to sum of all elements of the array.

Try

1

3 6

1 2 3

Comment if you want me to fix it

What's wrong with the proof provided?

Another solution is to sort the arrays by comparing pairs $$$(min(a_{i,1}, a_{i,2}), max(a_{i,1},a_{i,2}))$$$. We can observe that if we move the array with minimal element to the left (and among these with the least maximum), the number of inversions cannot increase, so that's optimal order

A simpler solution for 1E:

When you choose a node as the root node, our answer is at least $$$\sum_{i=1}^n \frac12 s_i(s_i-1)$$$, where $$$s_i$$$ is the number of children of node $$$i$$$.

However, such a construction may not be able to satisfy some edges that pass through both the son and father at the same time. Let's consider the contribution of this situation to increasing the answer.

We set a dp state $$$f_i$$$ to represent the number of residual paths that can be uploaded through the parent when the node $$$i$$$ calculates the necessary contribution internally (i.e., the above equation).

Transfer as follows:

$$$f_u = \sum_{v\in son_u} \max(1 - [u\text{ is root}], f_v - (s_u - 1))$$$

After calculating $$$f_ {root}$$$, we must pair the extra paths pairwise, and when we choose the node with the highest degree as the root, we can prove that there must be a match to make the scheme valid:

[tbd, prove is hard]

So we can calculate $$$f_ {root}$$$ and add it to the equation at the beginning.

using translator.

287001804

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
long long dp[MAXN]; vector<int> G[MAXN];
long long ans = 0;
void dfs(int u, int f) {
	int d = 0; for (int v : G[u]) if (v != f) dfs(v, u), d++;
	dp[u] = 0; for (int v : G[u]) if (v != f) dp[u] += max((u == f ? 0ll : 1ll), dp[v] - (d - 1));
	ans += 1ll * d * (d - 1) / 2;
}
int main() {
	int t; scanf("%d", &t); while (t--) {
		int n; scanf("%d", &n);
		for (int i = 1; i <= n; i++) G[i].clear();
		for (int i = 1; i < n; i++) {
			int u, v; scanf("%d %d", &u, &v);
			G[u].push_back(v); G[v].push_back(u);
		}
		int rt = 1; for (int i = 2; i <= n; i++) if (G[i].size() > G[rt].size()) rt = i;
		ans = 0; dfs(rt, rt);
		printf("%lld\n", ans + (dp[rt] + 1) / 2);
	}	
}