P9755

· · 题解

闲话

场切了，但是被卡常了，而且快读没判负数，寄飞了/px

这次 CSP-S 是不是没有放防阿克的题啊，T4 我竟然能做出来/jy

Problem

link：https://www.luogu.com.cn/problem/P9755。

Solution

首先一眼答案具有单调性，然后一眼二分答案，那么就要考虑 check 函数怎么写。

考虑我们现在在判断时刻 m 是否合法，那么我们对于每个点再去求一个值 t_i 代表最晚要在第 t_i 时刻把这个点的树种上。则 t_i=\max\limits_{\sum\limits_{j=x}^m \max\{b_i+j\cdot c_i,1\}\ge a_i}{x}。

则问题在于如何快速计算 f(m)=\sum\limits_{j=1}^m \max\{b_i+j\cdot c_i,1\}。

其实这是好做的（小学奥数/yiw），考虑到 \sum\limits_{j=1}^m b_i+j\cdot c_i 和 \sum\limits_{j=1}^m 1 都是好求的，那么我们要把那个 \max 给去掉。

方便起见，设 g(x)=\sum\limits_{i=1}^x i=\frac{x(x+1)}{2}。

观察到 b_i,c_i 和 1 是定值，则 y=b_i+c_i\cdot x 和 y'=1 至多只有一个交点：

需要注意的是，笔者在代码实现中 x_0 是上取整，所以可能与刚才推的柿子略有不同。

此外 x_0 应当向 0 取 \max，向 m 取 \min。

由于 f(m) 具有单调性，则 f(m)-f(x) 同样具有单调性，对于 t_i 二分求即可。

得到 t_i 后，我们贪心地将所有点按 t_i 排序，然后依次从其一直向根节点种树。邻项交换易证。

但是由于我们每次种树是要将其到根节点全部种上树，而且每个节点不能重复种，相当于路径覆盖全 1，全局查询当前有几个 1。如果直接树剖暴力做，复杂度是 \Theta(n\log V\log^2 n) 的，显然过不去。

但是我们考虑到一个节点只会被种一次，而且如果某个节点已经被种过了，其所有祖先节点必然也被种过，所有我们每次只需要暴力跳父亲，然后打上一个代表已经填过的 tag，遇到如果某个父亲已经被种过就 return，均摊复杂度 \Theta(n)。

最终复杂度瓶颈在于两个二分和排序，时间复杂度为 \Theta(n\log V\log n)。

Code

#include<bits/stdc++.h>
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define ll long long
//#define int long long
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define cl(f,x) memset(f,x,sizeof(f))
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
using namespace std;
const int N=1e5+5;
int head[N],len;
struct node {
    int to,nxt;
}; node edge[N<<1];
void add_edge(int u,int v) {
    edge[++len]={v,head[u]}; head[u]=len;
}
int f[N];
void dfs(int u,int fa) {
    f[u]=fa;
    for(int i=head[u];i;i=edge[i].nxt) {
        int v=edge[i].to;
        if(v!=fa)
            dfs(v,u);
    }
}
__int128 calc(__int128 x) {
    return x*(x+1)/2;
}
const __int128 awa=1;
inline __int128 calc(__int128 a,__int128 b,__int128 c) {
    __int128 x=max(awa,min(a+1,(__int128)ceil(1.0*(1-b)/c)));
    if(c<0)
        return (x-1)*b+calc(x-1)*c+(a-x+1);
    else if(c==0)
        return a*b;
    else
        return (x-1)+(a-x+1)*b+(calc(a)-calc(x-1))*c;
}
ll a[N],b[N],c[N];
int p[N],t[N],n;
bool used[N];
int update(int u) {
    if(used[u])
        return 0;
    used[u]=true;
    if(f[u])
        return update(f[u])+1;
    return 1;
}
bool check(int x) {
    rep(i,1,n) {
        used[i]=false;
        __int128 val=calc(x,b[i],c[i]);
        if(val<a[i])
            return false;
        int l=1,r=n,ans=-1;
        while(l<=r) {
            int mid=(l+r)>>1;
            if(val-calc(mid-1,b[i],c[i])>=a[i])
                ans=mid,l=mid+1;
            else
                r=mid-1;
        }
        t[i]=ans;
    }
    sort(p+1,p+n+1,[](const int &x,const int &y) {
        return t[x]<t[y];
    });
    int res=0;
    rep(i,1,n) {
        res+=update(p[i]);
        if(res>t[p[i]])
            return false;
    }
    return true;
}
ll read() {
    ll x=0,f=1; 
    char ch=getchar();
    while(!isdigit(ch)) {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
        x=x*10+ch-48,ch=getchar();
    return x*f;
}
int main() {
    n=read();
    rep(i,1,n)
    a[i]=read(),b[i]=read(),c[i]=read(),p[i]=i;
    rep(i,2,n) {
        int u=read(),v=read();
        add_edge(u,v);
        add_edge(v,u);
    }
    dfs(1,0);
    int l=n,r=1e9,ans=1e9;
    while(l<=r) {
        int mid=(l+r)>>1;
        if(check(mid))
            r=mid-1,ans=mid;
        else
            l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}