D

首先把一条路径拆成到 LCA 的两条链，考虑枚举较长的一条链的长度。

假设较长一条链的端点是 ，长度为 ，那么 不能落在前 层，因为这条链的长度比 小。

所以 可选的点数为

等比数列求和就是

对于链的另一个端点 ，其长度为 ，并且可以在树的其他部分随意取， 只要不落在 LCA 的 所在子树就行，那么我们有 个子树可以选，每个子树内再向下延伸 层，则答案为

和 的方案数乘起来就是答案，注意特判 的情况没有 的一段，且 时两段对称，要除以 。

#include <bits/stdc++.h>
using i64 = int64_t;

constexpr i64 mod = 1e9 + 7;

inline i64 f_pow(i64 a, i64 k) {
	i64 base = 1;
	for (; k; k >>= 1, a = a * a % mod)
		if (k & 1)
			base = base * a % mod;
	return base;
}

int main() {
	i64 n, m, k;
	std::cin >> n >> m >> k;

	i64 ans = 0;
	i64 invk = f_pow(k - 1, mod - 2);
	i64 inv2 = f_pow(2, mod - 2);
	i64 tot = ((f_pow(k, n) - 1) * invk % mod + mod) % mod;

	for (int i = std::min(m, n); i >= ((m + 1) >> 1); i--) {
		i64 u = ((tot - (f_pow(k, i) - 1) * invk % mod) + mod) % mod;

		i64 v = (i == m ? 1 : (k - 1) * f_pow(k, m - i - 1) % mod);
		i64 inv = (i * 2 == m ? inv2 : 1);

		ans = (ans + (u * v % mod * inv % mod)) % mod;
	}
	std::cout << ans << '\n';
	return 0;
}

F

首先这个所有数出现两次或零次的限制可以考虑成异或和为 ，给每一个值随机一个大权值异或就能保证正确可能性非常高，但是这样只能保证所有数出现次数为偶数次。

我场上的想法就是找到一个版本使得所有数出现次数不超过 ，然后统计这个区间内有多少个前缀异或和 当前位置前缀异或和，可惜我场上往可持久化去想了，实际上并不需要可持久化。

注意到，如果我们在加入 后，某一个位置 不满足所有数出现次数不超过 ，那么其前面的位置也不能满足，并且最后一个不满足的位置只会向后移动，是单调的，可以用一个指针维护，事实上也只能这样维护。

所以我们实际上只要枚举右端点 ，双指针维护一段可行区间，维护可行区间里面的所有位置 代表的前缀异或和 ，查询时只需要知道 与多少个前缀异或和相等即可。

#include <bits/stdc++.h>
using i64 = int64_t;
using u64 = uint64_t;

std::random_device seed;

void solve() {
    int n;

    std::cin >> n;
    std::vector<i64> a(n + 1, 0);
	std::mt19937_64 rnd(seed());

	for (int i = 1; i <= n; i++)
		std::cin >> a[i];

	std::map<int, u64> val;
	for (int i = 1; i <= n; i++)
		if (!val[a[i]])
			val[a[i]] = rnd();

	std::map<u64, int> cnt;
	std::map<int, int> rcnt;
	std::vector<u64> pre(n + 1, 0);

	pre[0] = 1;
	i64 ans = 0;
	cnt[1] = 1;

	int i = 1, j = 1;

	while (i <= n) {
		rcnt[a[i]]++;

		while (j <= i && rcnt[a[i]] > 2) {
			cnt[pre[j - 1]]--;
			rcnt[a[j++]]--;
		}
		
		pre[i] = pre[i - 1] ^ val[a[i]];
		ans += cnt[pre[i]];
		cnt[pre[i++]]++;
	}
	std::cout << ans << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int T;
    std::cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}