前言
NOIP 模拟考到了这题，整场比赛死磕这题，最后悲痛拿下 \(\text{0 + 30 + 0 + 0 = 30pts}\) 的高分。
Solution
题意很清楚。每一次染色操作当且仅当父亲节点染过色。每一个节点贡献的价值是点权乘上时间。求贡献和最小。
设当前权值最大的节点为 \(x\)，那么如果 \(x\) 之前的节点被染过色了，\(x\) 就一定要染色。不妨将 \(x\) 与之前的节点合并成一个块。
对于每一个块，我们需要判断如何调整先后顺序来使得贡献最小。先给一个贪心结论吧：根据平均数从大到小。
如何证明？
对于两个块 \(A\) 和 \(B\)，我们设它们的大小分别为 \(n\) 和 \(m\)。
-
若将 \(A\) 排在 \(B\) 前进行操作，贡献即为 \(\sum\limits_{i=1}^{n} A_i \times i +\sum\limits_{i=1}^{m} B_i \times (i+n)\)。
-
若将 \(B\) 排在 \(A\) 前进行操作，贡献即为 \(\sum\limits_{i=1}^{m} B_i \times i +\sum\limits_{i=1}^{n} A_i \times (i+m)\)。
相减得出：\(m\sum\limits_{i=1}^{n} A_i-n\sum\limits_{i=1}^{m} B_i\)。
当该值 \(>0\) 时，也就是如下时，\(A\) 排在 \(B\) 前进行操作贡献更小。否则反之：
\[m\sum\limits_{i=1}^{n} A_i-n\sum\limits_{i=1}^{m} B_i>0 \]\[m\sum\limits_{i=1}^{n} A_i>n\sum\limits_{i=1}^{m} B_i \]\[\frac{\sum\limits_{i=1}^{n} A_i}{n}>\frac{\sum\limits_{i=1}^{m} B_i}{m} \]易发现，这便是 \(A\) 和 \(B\) 两者的平均数。
证毕。
使用并查集维护块的大小、总和以及“平均数”，使用大根堆维护当前权值最大的节点即可。时间复杂度 \(\mathcal{O}(n \log n)\)。
话说题解区为什么大部分都是 \(\mathcal{O}(n^2)\) 的啊，明明使用堆优化就可以优化到 \(\mathcal{O}(n \log n)\) 啊（
Code
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
int t,n,rt,ans=0;
struct node{
int fa,sum,siz;
double val;
}qwq[114514];
int f[114514];
int now=0;
bool vis[114514];
priority_queue<pair<double,int> > q;
int find(int x){
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
signed main(){
while(1){
n=read(); rt=read();
ans=0; now=0;
if(!n&&!rt) break;
for(int i=1;i<=n;i++) qwq[i]=(node){0,0,0,0.0};
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=n;i++) qwq[i].siz=1;
for(int i=1;i<=n;i++) vis[i]=false;
for(int i=1;i<=n;i++){
qwq[i].sum=read();
ans+=qwq[i].sum;
if(i^rt) q.push(make_pair(qwq[i].sum,i));
}
for(int i=1;i<n;i++){
int u,v;
u=read(); v=read();
qwq[v].fa=u;
}
while(!q.empty()){
int x=q.top().second;
q.pop();
if(vis[x]) continue;
vis[x]=true;
int fa=find(qwq[x].fa);
ans+=qwq[fa].siz*qwq[x].sum;
qwq[fa].siz+=qwq[x].siz;
qwq[fa].sum+=qwq[x].sum;
f[x]=fa;
if(fa!=rt) q.push(make_pair((double)((1.0*qwq[fa].sum)/(1.0*qwq[fa].siz)),fa));
}
printf("%lld\n",ans);
}
return 0;
}