P9755 [CSP-S 2023] 种树 卡常题解

前言

赛时没过，赛后乱糊！这个做法本来过了洛谷数据的，但是 CCF 数据太强了，竟然只有 40pts？？？

而且这个做法有点卡常，需要修改一下，还是能跑过。

正文

0x00 分析题目

第一眼看着这个题肯定是想要贪心去搞，但是发现不同时间种下一棵树，由于题目中的计算方式，最后需要的长高的时间并不一样的，所以肯定不能普通地贪心。既然不好确定开始时间，那就考虑确定结束时间。观察到答案具有单调性，考虑二分答案，这样确定了一个生长的结束时间后，很容发现开始时间需要满足的条件很简单，小于等于某个时间点即可。考虑对于每个节点 $u$ 把这个东西算出来，记作 $t_u$。现在就可以进行贪心了。

考虑从根节点开始向下扩散，选择点种树，具体来说维护一个以 $t_u$ 为关键字的小根堆，每次选择小根对顶部点 $u$ 进行种树，看当前时刻是否小于等于 $t_u$，然后遍历其儿子 $v$，把 $v$ 放入小根堆。这样就能保证种某一颗树时，其祖先全部种上了树。但是直接这样做并不对，因为一个点的 $t_u$ 可能看起来很大，但是其子树内可能有个点的 $t_v$ 很小，所以需要把 $t_u$ 处理一下：

$$t_u=\min_{v\in tree_u} t_v$$

变成子树内最小的值，即可。

0x01 代码实现

记 $F_{s,t,u}$ 表示 $u$ 这个树在 $\left[s,t\right]$ 这段时间内生长高度，那么有：

$$F_{s,t,u}=\sum_{i=s}^{t}\min\left(b_i+c_i\times i,1\right)$$

当 $\forall i\in\left[s,t\right],b_i+c_i\times i\geq 1$ 时：

$$F_{s,t,u}=\frac{\left(s+t\right)\left(t-s+1\right)c_u}{2}+\left(t-s+1\right)b_u$$

其他情况下，不妨算出 $p_u$ 使得 $i=p_i,b_i+c_i\times i\lt 1$，显然：

$$p_u=\lfloor\frac{b_u-1}{-c_u}\rfloor$$ $$F_{s,t,u}=F_{s,p_u,u}+t-p_u+1$$

对于求出 $t_u$，不想推式子的话二分就好了，用 $F_{s,t,u}$ 去 check。

发现 $F_{s,t,u}$ 会超过 $2^{64}$，但是不会超过 $2^{128}$，可以选择用 int128 记录，但是这样会被卡常。然后可以发现长得太高没有用于是可以算出个 int128 然后和 $1e18$ 取 $\min$ 即可。

AC CODE

#include<bits/stdc++.h>
// #define ONLINE_JUDGE
#define INPUT_DATA_TYPE long long
#define OUTPUT_DATA_TYPE long long
INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10^48);return;}

std::vector<int> e[100010];

void addEdge(int u,int v){
	e[u].push_back(v);
	return;
}

int n;
long long a[100010],b[100010],c[100010],tim[100010],p[100010];
std::bitset<100010> vis;

struct NODE{
	long long w;
	int u;
	bool operator < (const NODE o) const{
		return w>o.w;
	}
};

std::priority_queue<NODE> Q;

long long abss(long long x){return x<0?-x:x;}
long long floor_(long long a,long long b);
long long ceil_(long long a,long long b){
    if(a>=0&&b>=0) return (a+b-1)/b;
    else if(a<0&&b<0) return ((-a)+(-b)-1)/(-b);
    else return -floor_(abss(a),abss(b));
}
long long floor_(long long a,long long b){
    if(a>=0&&b>=0) return a/b;
    else if(a<0&&b<0) return (-a)/(-b);
    else return -ceil_(abss(a),abss(b));
}

long long getH(long long start,long long end,int u){
	if(start>end) return 0;
	if(c[u]<0&&p[u]+1<=end) return std::min((__int128_t)std::max(end-std::max(p[u]+1,start)+1,0ll)+(__int128_t)getH(start,p[u],u),(__int128_t)0x3f3f3f3f3f3f3f3fll);
	return std::min((__int128_t)(start+end)*(__int128_t)(end-start+1)/2*(__int128_t)c[u]+(__int128_t)b[u]*(__int128_t)(end-start+1),(__int128_t)0x3f3f3f3f3f3f3f3fll);
}

long long calc(long long end,int u){
	register long long l=1,r=end,mid;
	while(l<r){
		mid=(l+r)>>1;
		if(getH(mid,end,u)>=a[u]) l=mid+1;
		else r=mid;
	}
	return l;
}

void getPri(int u,int p){
    for(auto v:e[u])
        if(v!=p)
            getPri(v,u),tim[u]=std::min(tim[u],tim[v]);
    return;
}

bool solve(long long ans){
	register int i,u,v;
	register long long now=1;
	for(i=1;i<=n;++i) tim[i]=calc(ans,i),vis[i]=0;
	for(i=1;i<=n;++i) if(getH(tim[i]-1,ans,i)<a[i]||tim[i]==1) return false;
    getPri(1,1);
	while(!Q.empty()) Q.pop();
	Q.push((NODE){0,1});
	while(!Q.empty()){
		u=Q.top().u,Q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		if(now>=tim[u]) return false;
		for(auto v:e[u])
			if(!vis[v])
				Q.push((NODE){tim[v],v});
		++now;
	}
	return true;
}

int main(){
	register int i,flg=0,u,v;
	register long long l,r=1000000010ll,mid;
	n=read();
	for(i=1;i<=n;++i){
		a[i]=read();
		b[i]=read();
		c[i]=read();
		flg|=c[i];
		if(c[i]<0) p[i]=((b[i]-1)/(-c[i]));
	}
	for(i=1;i<n;++i){
		u=read();
		v=read();
		addEdge(u,v);
		addEdge(v,u);
	}

	l=0;
	while(l<r){
		mid=(l+r)>>1;
		if(solve(mid)) r=mid;
		else l=mid+1;
	}
	print(l);

    return 0;
}