题解 CF1205D【Almost All】
whiteqwq
2021-12-12 17:22:13
[CF1205D Almost All](https://www.luogu.com.cn/problem/CF1205D) 解题报告：
[更好的阅读体验](https://www.cnblogs.com/xiaoziyao/p/15679743.html)
## 题意
给定一颗 $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)$。
## 代码
```cpp
#include<stdio.h>
#include<vector>
#include<algorithm>
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];
vector<int>v[maxn];
void dfs(int x,int last,int f){
sz[x]=1;
for(int i=0;i<v[x].size();i++)
if(v[x][i]!=last)
dfs(v[x][i],x,f),sz[x]+=sz[v[x][i]],val[x]=max(val[x],sz[v[x][i]]);
val[x]=max(val[x],n-sz[x]);
if(f==0&&(p==0||val[p]>val[x]))
p=x;
}
inline int cmp(int a,int b){
return sz[a]<sz[b];
}
void get(int x,int last,int val){
fa[x]=last,dfn[x]=(++dfns)*val;
for(int i=0;i<v[x].size();i++)
if(v[x][i]!=last)
get(v[x][i],x,val);
}
int main(){
scanf("%d",&n);
for(int i=1,x,y;i<n;i++)
scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
dfs(1,0,0),dfs(p,0,1);
for(int i=0;i<v[p].size();i++)
id[++ids]=v[p][i];
sort(id+1,id+1+ids,cmp);
int sum=0,k;
for(int i=1;i<=ids;i++){
ok[id[i]]=1,sum+=sz[id[i]],get(id[i],p,1);
if(sum>=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;
}
```