题解
刚开始想了半天以为是什么简单的性质比如说子树权值和的关系，但是这个等差数列加权就很恶心呀根本不知道怎么搞。
首先我们需要贪心考虑一些东西，发现如果一个非根节点的权值如果是当前整棵树里最大的，那么当它的父亲被选的时候下一个选的肯定就是它，否则通过调整法显然能得到更小的权值和。这个调整就不仔细说了算比较简单的。
然后我们考虑逆向思维，将这样类型的点合并起来，在合并的过程中其实也间接找到了选择的顺序。
但是合并起来有个问题，上面那个性质只是针对非根单节点，那合并起来怎么比较点之间的优先级呢？
于是有一个加强版结论：所在点的权值和与点个数的比值越大，越先合并
我们来证明这个结论
记当前上述比值最大的点为 $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$太弱了
0 条评论