2023CSPS 种树 二分 前缀和,小熊种树二年级作文

This way

题意

    一开始以为是水题敲了一个二分贪心检查的代码20分。发现从根往某个节点x走的时候一路走来的子树上的节点到已栽树的节点的距离会变短那么并不能按照初始情况贪心。
    于是就想着检查时候用线段树存的是(每个节点最晚开始时间-它距离最近栽树的点的距离)往后就将这个称为ddl。每一步都往当前最小值的位置走每走一步将当前这一步的子树区间1如此往复。当走到一个点发现已经走的步数>这个点最晚开始时间时候就是not。但是代码过于繁杂最终放弃了这样思路而且常数可能会比较大最终如果TLE了血亏。
    首先这道题的答案满足二分的性质考虑使用二分。二分出来结束时间的时候我们可以求出每个点的最晚到达时间首先分c>0和c<0两种情况。对于c<0的时候又要分三种情况。其实就是等差数列求和公式但是注意会爆longlong所以转乘为除。我这里使用二分去找答案当然直接算好像也行
    发现其实每个点的ddl就是它子树的ddl最小值也就是每个点的ddl可视为子树中最小ddl-当前点到ddl最小的节点的距离例如

假设点1的最晚开始时间是第10天点2是第3天点3是第50天点4是第90天点5是第4天。那么转换过来其实它们真实的ddl如下

    这个时候我们只需要将所有真·ddl存到桶里面再做一个前缀和记为num[i]。若i<num[i]则表示你走了i步但是有超过i个点的ddl在i步之内我们在上图处理完之后所有链上的ddl必然是递增的也就是如果点x需要走10步那father[x]最大为9,father[father[x]]最大为8也就是为x做铺垫那么表示无法在i步内满足num[i]个点的ddl。

#include<bits/stdc.h>using namespace std;#define ll long longconst int N1e55;ll a[N],b[N],c[N],en[N],e,shou,mo;int n,x,y,dep[N],u,tim,num[N],t[N];vector<int>vec[N];bool vis[N];#define pii pair<int,int>vector<pii>day;int dfs(int x,int fa){    for(int ne:vec[x]){        if(nefa)continue;        t[x]min(t[x],dfs(ne,x)-1);    }    num[t[x]];    return t[x];}bool check(ll d){    day.clear();    memset(num,0,sizeof num);    for(int i1;i<n;i){        ll l1,rmin(1ll*n,d);t[i]-1;        while(l<r){            ll xlr>>1;            if(c[i]>0){                if((a[i]*2lld-x)/(d-x1)<2*b[i](xd)*c[i])t[i]x,lx1;                else rx-1;            }            else{                c[i]-c[i];                if(en[i]<x){                    if(a[i]<d-x1)t[i]x,lx1;                    else rx-1;                }                else if(en[i]<d){                    een[i]-1;                    shoub[i]-x*c[i],mob[i]-e*c[i];                    if((2*a[i]-2*(d-e)e-x)/(e-x1)<(shoumo))t[i]x,lx1;                    else rx-1;                }                else{                    ll shoub[i]-x*c[i],mob[i]-d*c[i];                    if((2*a[i]d-x)/(d-x1)<(shoumo))t[i]x,lx1;                    else rx-1;                }                c[i]-c[i];            }        }        if(t[i]-dep[i]<0)return 0;    }    dfs(1,0);    for(int i1;i<n;i){        num[i]num[i-1];        if(num[i]>i)            return 0;    }    return 1;}int main(){    ll ln,r0,ans-1;    scanf(%d,&n);    for(int i1;i<n;i){        scanf(%lld%lld%lld,&a[i],&b[i],&c[i]);        rmax(r,a[i]);        if(c[i]<0)            en[i](b[i]-c[i]-1)/(-c[i]);    }    rmin(r,1000000000ll);    for(int i1;i<n;i){        scanf(%d%d,&x,&y);        vec[x].push_back(y),vec[y].push_back(x);    }    while(l<r){        ll midlr>>1;        if(check(mid))rmid-1,ansmid;        else lmid1;    }    printf(%lld\n,ans);    return 0;}