昨晚 CF E

cjdst

2026-07-20 12:58:22

发布于：广东

22阅读

0回复

0点赞

太困了，切了两题就睡了。

哦不不不这无疑是困难的，看到这题我无疑是害怕的。

听机房同学讲题，听懂了。

考虑以 $n$ 为根，其余奇偶分组，每一组都直接接在 $n$ 下面。此时每一个贡献路径都要经过 $n$ ，所以答案为所有点的深度和的两倍。显然这么构造上下界都能取到。

令点较多的组为 $S_1$ ，较少的组为 $S_2$ （upd：这个 $S_1,S_2$ 大小疑似没关系），因此我们需要构造 $\sum dep_{S_{1,i}}+\sum dep_{S_{2,i}}=\frac{k}{2}$ 。

随便构造一组 $x,y$ ，使得 $x+y=\frac{k}{2},x\ge |S_1|,y\ge |S_2|,x\le \frac{|S_1|(|S_1|+1)}{2},y\le \frac{|S_2|(S_2|+1)}{2}$ ，然后让 $\sum dep_{S_{1,i}},\sum dep_{S_{2,i}}$ 分别为 $x,y$ 即可。

以 $S_1$ 为例。

然后就简单了：我们首先弄成一个链，然后把叶子节点深度逐个减一，直到答案减到 $x$ 。这个可以 $O(n)$ 实现。然后就做完了。

但我想不出来怎么办/jk

实现得有点史。

namespace cjdst{
    void solve(){
		ll n, k;
		std::cin >> n >> k;
		if(k % 2 || k < (n - 1) * 2){
			std::cout << "-1\n";
			return;
		}
		std::vector <int> s1, s2;
		std::vector <int> fa1, fa2;
		for(int i = 1; i < n; i++){
			if(i % 2) fa1.push_back(s1.empty() ? n : s1.back()), s1.push_back(i);
			else fa2.push_back(s2.empty() ? n : s2.back()), s2.push_back(i);
		}
		if(s1.size() < s2.size()){
			std::swap(s1, s2);
			std::swap(fa1, fa2);
		}
		if(1ll * s1.size() * (s1.size() + 1) / 2 + 1ll * s2.size() * (s2.size() + 1) / 2 < k / 2){
			std::cout << "-1\n";
			return;
		}
		auto solve2 = [&](std::vector <int> &s, std::vector <int> &fa, ll val) -> bool{
			val = ll(1ll * s.size() * (s.size() + 1) / 2) - val;
			if(val < 0) return 0;
			int cur = s.size() - 1;
			while(cur >= 0){
				if(val <= cur){
					while(val--){
						fa[cur] -= 2;
						if(fa[cur] <= 0) fa[cur] = n;
					}
					break;
				}
				fa[cur] = n;
				val -= cur;
				cur--;
			}
			return 1;
		};
		ll cur;
		if(k / 2 >= 1ll * s1.size() * (s1.size() + 1) / 2 + s2.size()) cur = 1ll * s1.size() * (s1.size() + 1) / 2;
		else cur = k / 2 - s2.size();
		if(solve2(s1, fa1, cur) && solve2(s2, fa2, k / 2 - cur)){
			for(int i = 0; i < s1.size(); i++){
				std::cout << s1[i] << ' ' << fa1[i] << '\n';
			}
			for(int i = 0; i < s2.size(); i++){
				std::cout << s2[i] << ' ' << fa2[i] << '\n';
			}
		}else{
			std::cout << "-1\n";
		}
	}
}

时间复杂度： $O(\sum n)$ 。

有帮助，赞一个

去预览

0/2000

全部评论 1

cjdst
d

2026-07-20 来自广东
0

全部评论 1

热门讨论