P12491 题解

· · 题解

基础点分治练习题，感觉挺典的，很适合我这种入门点分治的人阿。

维护路径信息想到点分治。对于当前分治重心 u 可以处理出子树内所有点 v 到它的路径点权 \min 和 \sum，设其为 p_v,q_v。

那么限制就是找到路径 (v_1,v_2) 使得 \min(p_{v_1},p_{v_2})\times (q_{v_1}+q_{v_2}-b_u)\ge V。

那么倒序去扫描线 p_v 维护当前 v 作为路径端点之一的答案。那么 \min p=p_v 这样就消去了一维。有：

p_v\times(q_v+q_{x}-b_u)\ge V\\q_x\ge\lceil\frac{V}{p_v}\rceil-q_v+b_u

我们需要找到满足条件的最小的 q_x，这样 (x,v) 可以贡献答案 q_v+q_x-b_u。

维护后缀信息，随便上数据结构像什么 Fenwick 或者 SGT 都可以乱做。

但是有一个不一样的点是，一般的点分治统计路径的时候，我们习惯用容斥去做，用全局贡献减去每棵子树内部贡献。本题要求最小值所以不支持减法，所以不支持容斥做。

所以我们必须在全局统计答案的时候就过滤掉在同一子树内的路径。具体的，给每个点打上颜色 col，从 u 出发的某子树 son 内的所有点的颜色为 son，u 自己本身的颜色为 u。我们需要强制要求选出来的 (v_1,v_2) 颜色不同。

也就是说，扫描到当前点 v 时，我们需要在之前扫过的点中找到 q_x\ge\lceil\frac{V}{p_v}\rceil-q_v+b_u 且 col_v\ne col_x 的最小的 q_x。

如果直接 Fenwick 维护的话，得到的最小值可能与当前点 v 同色，无法得到正确答案。所以对于 Fenwick 上每个节点，多维护一份信息，即维护四元组 (w_1,c_1,w_2,c_2)，表示最小和次小的 q 值且需满足 c_1\ne c_2。由于 v 只排斥 col_v 一种颜色所以记录两个异色的信息就能覆盖所有情况。

具体维护啥的都挺简单吧。这里不讲了。最后漏了一种 corner case 是当前分治重心 u 单独作为一条链存在的情况，补算一下即可。

#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=2e5+5,inf=0x3f3f3f3f3f3f3f3f;
int n,K,tot,ans,root,a[N],b[N],vis[N],siz[N],dp[N];
vector<int>v[N];
struct node{int mn,sum,col;}st[N];
struct BIT{
    struct nd{int v1,c1,v2,c2;}tr[N];
    void init(int x){for(int i=1;i<=x;i++)tr[i]={inf,0,inf,0};}
    inline int lb(int x){return x&(-x);}
    nd uni(nd x,nd y){
        if(x.v1>y.v1)swap(x,y);
        if(x.c1==y.c1){if(y.v2<x.v2)x.v2=y.v2,x.c2=y.c2;}
        else{if(y.v1<x.v2)x.v2=y.v1,x.c2=y.c1;}
        return x;
    }
    void upd(int x,int val,int c,int X){
        int id=X-x+1;
        nd tmp={val,c,inf,0};
        while(id<=X)tr[id]=uni(tr[id],tmp),id+=lb(id);
        return;
    }
    nd qy(int x,int X){
        int id=X-x+1;
        nd res={inf,0,inf,0};
        while(id)res=uni(res,tr[id]),id-=lb(id);
        return res;
    }
}T;
void fd(int x,int fa,int now){
    siz[x]=1,dp[x]=0;
    for(int i=0;i<v[x].size();i++){
        int to=v[x][i];
        if(to==fa||vis[to])continue;
        fd(to,x,now),siz[x]+=siz[to],dp[x]=max(dp[x],siz[to]);
    }
    dp[x]=max(dp[x],now-siz[x]);
    if(dp[x]<dp[root])root=x;
    return;
}
void calc(int x,int fa,int mn,int sum,int col){
    st[++tot]={mn,sum,col};
    for(auto to:v[x]){
        if(vis[to]||to==fa)continue;
        calc(to,x,min(mn,a[to]),sum+b[to],col);
    }
    return;
}
bool cmp(node x,node y){return x.mn>y.mn;}
void sol(int x){
    tot=0,st[++tot]={a[x],b[x],x};
    for(auto to:v[x]){
        if(vis[to])continue;
        int od=tot;
        calc(to,x,min(a[x],a[to]),b[x]+b[to],to),siz[to]=tot-od;
    }
    vector<int>tmp;
    for(int i=1;i<=tot;i++)tmp.pb(st[i].sum);
    sort(tmp.begin(),tmp.end());
    tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
    int m=tmp.size();
    T.init(m);
    sort(st+1,st+tot+1,cmp);
    if(a[x]*b[x]>=K)ans=min(ans,b[x]);
    for(int i=1;i<=tot;i++){
        int tx=(K+st[i].mn-1)/st[i].mn-st[i].sum+b[x];
        auto it=lower_bound(tmp.begin(),tmp.end(),tx);
        if(it!=tmp.end()){
            int tt=it-tmp.begin()+1;
            auto res=T.qy(tt,m);
            int val=(res.c1!=st[i].col)?res.v1:res.v2;
            ans=min(ans,st[i].sum+val-b[x]);
        }
        int ty=lower_bound(tmp.begin(),tmp.end(),st[i].sum)-tmp.begin()+1;
        T.upd(ty,st[i].sum,st[i].col,m);
    } 
    return;
}
void dfs(int x){
    vis[x]=1,sol(x);
    for(int i=0;i<v[x].size();i++){
        int to=v[x][i];
        if(vis[to])continue;
        dp[0]=n,root=0,fd(to,x,siz[to]),dfs(root);
    }
    return;
}
signed main(){
    cin>>n>>K;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
    for(int i=1,x,y;i<n;i++){
        cin>>x>>y;
        v[x].pb(y),v[y].pb(x);
    }
    dp[0]=n,root=0,fd(1,0,n),ans=inf,dfs(root),cout<<ans;
    return 0;
}