CF1205D Almost All 解题报告

CF1205D Almost All 解题报告：

更好的阅读体验

题意

给定一颗 \(n\) 个点的树，构造树的边权使得对于 \(x\in[1,\lfloor\frac{2n^2}{9}\rfloor]\) 都存在一条路径使得路径边权和为 \(x\)。

\(1\leqslant n\leqslant 1000\)。

分析

nb 题。

首先容易构造出一种基本操作：对于一颗 \(n\) 个点的树，根到每个点的路径长度取遍 \(1,2,3,\cdots,n-1\)，只需要跑出 dfn 序然后边权等于相邻点 dfn 序之差即可。

考虑选择一个根，将儿子分成两个部分 A 和 B（大小分别为 \(p,q\)），A 部分使用上面的方法做出 \(1,2,\cdots,p\) 的路径长度，B 部分做出 \(1,2,\cdots,q\) 的路径长度，然后将所有边权乘 \((p+1)\)，容易发现这样可以拼凑出 \((p+1)(q+1)-1\) 的所有长度。

那么我们要选择出一组比较均衡的 \(p,q\) 满足 \((p+1)(q+1)-1\geqslant \lfloor\frac{2n^2}{9}\rfloor\)。

考虑怎么让 \(p,q\) 均衡：

首先选择重心为根，那么所有子树大小小于等于 \(\lfloor\frac{n}{2}\rfloor\)。

我们只需要将子树按照大小排序，选择一段前缀使得其恰好大于等于 \(\lfloor\frac{n}{3}\rfloor\) 即可，容易发现这些子树的大小之和不超过 \(2\lfloor\frac{n}{3}\rfloor\)。

计算可得上述构造符合条件，于是直接做即可，时间复杂度 \(O(n\log n)\)。

代码

#include
#include
#include
using namespace std;
const int maxn=1005;
int n,p,ids,dfns;
int sz[maxn],val[maxn],id[maxn],ok[maxn],fa[maxn],dfn[maxn];
vectorv[maxn];
void dfs(int x,int last,int f){
	sz[x]=1;
	for(int i=0;ival[x]))
		p=x;
}
inline int cmp(int a,int b){
	return sz[a]=n/3){
			k=i;
			break;
		}
	}
	dfns=0;
	for(int i=k+1;i<=ids;i++)
		get(id[i],p,sum+1);
	for(int i=1;i<=n;i++)
		if(i!=p)
			printf("%d %d %d\n",i,fa[i],dfn[i]-dfn[fa[i]]);
	return 0;
}