二分套二分+贪心：CSPS2023T4

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133991517

二分答案

再二分出每个点最晚什么时候被选

然后按照最晚被选的时间从前往后贪心

暴力跳即可

复杂度 O(nlog⁡2n)O(n\log^2n)

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<bits/stdc++.h>
using namespace std;
#define int __int128
#define ll long long
//#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;
}
void print(int a) {
	if(a/10) print(a/10); 
	putchar(a%10+'0'); 
}
ll zh(int a) {
	if(a/10) return zh(a/10)*10+(ll)(a%10); 
	return (ll)(a%10); 
}
#define pb push_back
#define N 200010
//#define M
//#define mo
struct node {
	int a, b, c, id, d; 
}a[N];
int ceil(int a, int b) {
	return a / b + (a % b ? 1 : 0); 
}
int n, m, i, j, k, T, flg, u, v, f[N], w[N], p[N];
vector<int>G[N]; 

void dfs(int x, int fa)  {
	f[x] = fa; 
	for(auto y : G[x]) 
		if(y != fa) dfs(y, x); 
}

int S(int l, int r, int n) {
	return (l + r) * n / 2; 
}
	
namespace Sol {
	int l, r, mid, s, t, i, j, vis[N]; 
	int suan(int i, int l) { //节点i从第r天到第l天 
		if(l == 0) return a[i].b; 
		if(a[i].c < 0) {
			if(l < p[i]) {
				int	shou = a[i].b; 
				int	mo = a[i].b + l * a[i].c; 
				return S(shou, mo, l+1); 
			} 
			if(l >= p[i]) return w[i]+(l-p[i]+1); 
		}
		else {
			int	shou = a[i].b; 
			int	mo = a[i].b + l * a[i].c; 
			return S(shou, mo, l+1); 
		}
	}
	int check(int k) {
//		printf("Check : %lld\n", zh(k)); 
		sort(a+1, a+n+1, [] (node x, node y) { return x.id < y.id; }); 
		for(i=1; i<=n; ++i) {
			l = 1; r = k; 
//			if(k==31) printf("%lld %lld\n", zh(suan(i, k)), zh(suan(i, 0))); 
			if(suan(i, k) - suan(i, 0) < a[i].a) return 0; 
			while(l < r) {
				mid = (l+r+1)>>1; 
//				printf("%lld [%lld %lld] : %lld %lld %lld\n", i, k, mid, suan(i, k), suan(i, mid-1), suan(i, k) - suan(i, mid-1)); 
				if(suan(i, k) - suan(i, mid-1) >= a[i].a) l=mid; 
				else r=mid-1; 
			}
			a[i].d=l; //最晚在第d天点亮 
////			printf("last %lld : %lld\n", zh(i), zh(a[i].d)); 
		}
		sort(a+1, a+n+1, [] (node x, node y) { return x.d < y.d; }); 
		memset(vis, 0, sizeof(vis)); 
		vis[1] = j = 1; 
		for(i=1; i<=n; ++i) {
			int x = a[i].id; 
			if(!vis[x]) {
				int y = x; 
				while(!vis[y]) y = f[y], ++j; 
				vis[x] = j; y = x; 
				while(!vis[f[y]]) vis[f[y]]=vis[y]-1, y=f[y]; 
			}
//			printf("vis[%lld] = %lld\n", zh(x), zh(vis[x])); 
			if(vis[x] > a[i].d) return 0; 
		}
//		printf("OK ! \n"); 
		return 1; 
	}
}

signed main() {
//	freopen("tree.in", "r", stdin);
//	freopen("tree.out", "w", stdout);
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	srand(time(0));
//	T=read();
//	while(T--) {
//	}
	n=read(); 
	for(i=1; i<=n; ++i)  {
		a[i].id=i; 
		a[i].a=read(); a[i].b=read(); a[i].c=read(); 
	}
	for(i=1; i<n; ++i) {
		u=read(); v=read(); 
		G[u].pb(v); G[v].pb(u); 
	}
	dfs(1, 0); 
	int l, r, mid; 
	for(i=1; i<=n; ++i)  
		if(a[i].c < 0)  {
			l = a[i].b / (-a[i].c) ; 
			for(j = l-3; j <= l+3; ++j) 
				if(a[i].b + j *a[i].c < 1) break; 
			p[i] = j ; // 从第p[i]天开始出事 
			int shou = a[i].b, mo = a[i].b + (j-1)*a[i].c; 
			w[i] = S(shou, mo, j); 
//			printf("%lld : %lld | %lld\n", zh(i), zh(p[i]), zh(w[i])) ;
		}
	l=n; r=1e9; 
	while(l < r) {
		mid = (l + r) >> 1; 
		if(Sol::check(mid)) r = mid; 
		else l = mid + 1; 
	}
	print(l); 
//	printf("%lld", l); 
	return 0;
}