树上优先队列维护贪心：2026暑杭电多校 1004 搭积木

1004 搭积木

感觉这个套路还是非常非常经典的，不知道我为什么忘了，还好队友带飞了。

我们考虑两棵子树 x,yx,y 分别连到一个大的连通块上，先连谁，推一推式子可以发现，如果先 xx 后 yy，则：

bx×ay≤by×axb_x\times a_y\le b_y\times a_x

移项得：

axbx≥ayby\dfrac{a_x}{b_x}\ge \dfrac{a_y}{b_y}

所以这就很明显了，我们可以按 aibi\dfrac{a_i}{b_i} 进行排序。

由于这在树上，就变成了一个很经典的转化，我们直接用优先队列来维护上面这个式子。然后一个个加入维护，后面这个就显然了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
#define int long long
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;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 200010
struct node {
	int x, a, b; 
	bool operator < (const node &A) const {
		return a * A.b < b * A.a; 
	} 
};
priority_queue<node>q; 
int a[N], b[N]; 
int f[N], par[N], ans; 
int n, m, i, j, k, T;

int fa(int x) {
	if(f[x] == x) return x; 
	return f[x] = fa(f[x]); 
}

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
	T = read();
	while(T--) {
		n = read(); ans = m = 0; 
		for(i = 1; i <= n; ++i) a[i] = read(); 
		for(i = 1; i <= n; ++i) b[i] = read(); 
		for(i = 1; i <= n; ++i) par[i] = read(), f[i] = i; 
		for(i = 2; i <= n; ++i) q.push((node){i, a[i], b[i]}); 
		while(!q.empty()) {
			auto t = q.top(); q.pop(); 
			if(fa(t.x) != t.x || a[t.x] != t.a || b[t.x] != t.b) continue; 
			t.x = fa(t.x); ++m; 
			i = t.x; f[i] = par[i]; j = fa(par[i]); 
			debug("%lld [%lld]: %lld(%lld * %lld)\n", i, j, a[i] * b[j], a[i], b[j]); 
			ans += a[i] * b[j]; 
			b[j] += b[i]; a[j] += a[i];  
			if(par[j]) q.push((node){j, a[j], b[j]});  
		}
		printf("%lld\n", ans); 
	}

	return 0;
}