题解 CF1764F 【Doremy's Experimental Tree】

Leasier · 2022-11-30 14:48:06 · 题解

考虑先复原树的形态。这里我们先钦定以 1 为根。

我们抓出所有 f(i, 1)，将其从大到小排序，不难发现：

证明：首先 f(1, 1) 就是所有点的带权深度之和，它显然最大。

每次在 f(fa_u, 1) 的基础上添加一个 u，不难发现每个 x 的贡献不增，且存在一个会变小。

有了上述结论，我们依次考虑确定排序后每个点的父亲。类似地，注意到满足 f(v, 1) > f(u, 1) 且 f(u, v) 最大的 v 就是 fa_u。

于是我们还原了树的形态，现在考虑还原边权。

类似于换根 dp，我们希望通过 f(u, u) 与 f(u, fa_u) 的关系找出 (u, fa_u) 的边权。

这两者的区别是什么呢？注意到对于 u 子树外的点，前者的最小距离比后者多了一个 (u, fa_u) 的边权。

于是边权即为 \frac{f(u, u) - f(u, fa_u)}{n - size_u}。

时间复杂度为 O(n^2)。

代码：

#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdio>

using namespace std;

typedef long long ll;

typedef struct {
    int nxt;
    int end;
} Edge;

int cnt = 0;
int fa[2007], head[2007], size[2007];
ll f[2007][2007];
Edge edge[2007];
pair<ll, int> pr[2007];

inline int read_int(){
    int ans = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9'){
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9'){
        ans = ans * 10 + (ch ^ 48);
        ch = getchar();
    }
    return ans;
}

inline ll read_ll(){
    ll ans = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9'){
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9'){
        ans = ans * 10 + (ch ^ 48);
        ch = getchar();
    }
    return ans;
}

inline void add_edge(int start, int end){
    cnt++;
    edge[cnt].nxt = head[start];
    head[start] = cnt;
    edge[cnt].end = end;
}

void dfs(int u){
    size[u] = 1;
    for (int i = head[u]; i != 0; i = edge[i].nxt){
        int x = edge[i].end;
        dfs(x);
        size[u] += size[x];
    }
}

int main(){
    int n = read_int();
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= i; j++){
            f[i][j] = f[j][i] = read_ll();
        }
    }
    for (int i = 1; i <= n; i++){
        pr[i] = make_pair(f[i][1], i);
    }
    sort(pr + 1, pr + n + 1, greater<pair<ll, int> >());
    for (int i = 2; i <= n; i++){
        int pos = -1;
        for (int j = 1; j < i; j++){
            if (pos == -1 || f[pr[i].second][pos] < f[pr[i].second][pr[j].second]) pos = pr[j].second;
        }
        fa[pr[i].second] = pos;
        add_edge(pos, pr[i].second);
    }
    dfs(1);
    for (int i = 2; i <= n; i++){
        cout << i << " " << fa[i] << " " << (f[i][i] - f[i][fa[i]]) / (n - size[i]) << endl;
    }
    return 0;
}