题解

刚开始想了半天以为是什么简单的性质比如说子树权值和的关系,但是这个等差数列加权就很恶心呀根本不知道怎么搞。

首先我们需要贪心考虑一些东西,发现如果一个非根节点的权值如果是当前整棵树里最大的,那么当它的父亲被选的时候下一个选的肯定就是它,否则通过调整法显然能得到更小的权值和。这个调整就不仔细说了算比较简单的。

然后我们考虑逆向思维,将这样类型的点合并起来,在合并的过程中其实也间接找到了选择的顺序。

但是合并起来有个问题,上面那个性质只是针对非根单节点,那合并起来怎么比较点之间的优先级呢?

于是有一个加强版结论:所在点的权值和与点个数的比值越大,越先合并

我们来证明这个结论

记当前上述比值最大的点为 $u$,记 $sz[u]$为与 $u$点合并的点的个数,$w[u]$为权值和。如果说 $fa[u]$被选择之后,我们先选了一个点 $v$,再选 $u$。记选完 $u$和 $v$之后选剩余点的最小答案为 $rest$。

则先选 $u$再选 $v$的贡献和为

$$sz[u] \times w[v] + rest$$

而先选 $v$再选 $u$的贡献和为

$$sz[v]\times w[u] + rest$$

两式相减

$$(\frac{w[v]}{sz[v]} – \frac{w[u]}{sz[u]})(sz[u]sz[v])<0$$

所以先选 $u$的贡献和是最小的。

$Q.E.D.$

然后套这个结论用优先队列去维护就行了。

每次合并的时候记当前节点为 $u$,父亲节点为 $fa$,你可以每次将 $sz[fa]\times w[u]$加入贡献,也就相当于选完 $fa$节点里面的点后选 $u$的贡献 (意会一下 $QAQ$)

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<ctype.h>
#include<queue>
#include<map>
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define eps 1e-4
#define mod 10000000 
#define lowbit(x) (x & -x)
#define N 1105
#define clr(arr) memset(arr, 0, sizeof arr)
#define bset std::bitset<N>
inline int read ()
{
    Re int x = 0; Re bool flag = 0; Re char ch = getchar();
    while (!isdigit(ch) && ch != '-') ch = getchar();
    if (ch == '-') flag = 1, ch = getchar();
    while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    if (flag) x = -x; return x;
}
int n, rt, head[N], tot, fa[N];
struct edge {
    int nxt, v;
} e[N << 1];
inline void addedge (int u, int v)
{
    e[++tot] = (edge) {head[u], v};
    head[u] = tot;
}
struct node {
    int sz, w, id;
    friend bool operator < (node x, node y) { return x.w * y.sz < y.w * x.sz; }
};
std::priority_queue<node> q;
inline void dfs (int u, int F)
{
    fa[u] = F;
    edge (i, u)
    {
        if (v == F) continue;
        dfs(v, u);
    }
}
int sz[N], w[N], f[N], ans;
inline int find (int u) { return f[u] == u ? u : f[u] = find(f[u]); }
int main ()
{
    while ((n = read()) && (rt = read()))
    {
        ans = 0; tot = 0; clr(head); w[0] = sz[0] = 0;
        fo (i, 1, n) w[i] = read(), f[i] = i, sz[i] = 1, ans += w[i];
        fo (i, 2, n)
        {
            int u = read(), v = read();
            addedge(u, v);
            addedge(v, u);
        }
        dfs(rt, 0);
        fo (i, 1, n) if (rt != i) q.push((node) {1, w[i], i});
        while (!q.empty())
        {
            node u = q.top(); q.pop();
            if (u.sz != sz[u.id]) continue;
            f[u.id] = find(fa[u.id]); ans += w[u.id] * sz[f[u.id]];
            sz[f[u.id]] += sz[u.id]; w[f[u.id]] += w[u.id];
            if (f[u.id]) q.push((node) {sz[f[u.id]], w[f[u.id]], f[u.id]});
        }
        printf("%d\n", ans);
    }
    return 0;
}

然后你会发现这是一道双倍经验题,$HNOI2018$排列把这道题的结论反过来用就行了。不过这道题表述有点迷我还是看样例才转化过来的 $QwQ$太弱了

分类: 文章

quhengyi11

AFO 有缘再见

发表评论

电子邮件地址不会被公开。 必填项已用*标注