P12491 题解

· · 题解

Problem Link

题目大意

给定一棵树，每个点有两个权值 a_i,b_i。对于树上的一条简单路径，若这条路径上 b 之和乘上 a 的最小值大于等于一个常数 V，那么这条路径被称作一条好的路径，求所有好的路径中，\sum b 的最小值。

数据范围：n\le 2\times 10^5。

思路分析

点分治变成 (B_u+B_v)\min(A_u,A_v)\ge V，不妨设 A_u\le A_v，则只要找到最小的 B_v\ge \left\lceil \dfrac V{A_u}\right\rceil-B_u，并且 u,v 来自不同的子树。

那么按 A 降序加入每条路径，按 B 离散化后建树状数组，维护后缀最小值，限制不同的子树就维护不同色的最小值和次小值。

时间复杂度 \mathcal O(n\log^2 n)。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
const ll inf=2e18;
struct info {
    ll v1,v2;
    int c1,c2;
    inline friend info operator +(info u,info v) {
        if(u.v1>v.v1) swap(u,v);
        if(v.c1==u.c1) {
            if(v.v2<u.v2) u.v2=v.v2,u.c2=v.c2;
        } else if(v.v1<u.v2) u.v2=v.v1,u.c2=v.c1;
        return u;
    }
}   tr[MAXN],I={inf,inf,0,0};
int n,tp,siz[MAXN],cur[MAXN];
ll V,a[MAXN],b[MAXN],ans=inf;
vector <int> G[MAXN];
bool vis[MAXN];
ll st[MAXN];
void solve(int u) {
    if(a[u]*b[u]>=V) ans=min(ans,b[u]);
    vector <array<ll,3>> Q;
    for(int v:G[u]) if(!vis[v]) {
        function<void(int,int,ll,ll)> dfs3=[&](int x,int fz,ll mn,ll su) {
            mn=min(mn,a[x]),su+=b[x],Q.push_back({mn,su,v}),siz[x]=1;
            for(int y:G[x]) if(!vis[y]&&y!=fz) dfs3(y,x,mn,su),siz[x]+=siz[y];
        };
        dfs3(v,u,a[u],b[u]);
    }
    tp=0,sort(Q.begin(),Q.end(),greater<>());
    for(auto i:Q) st[++tp]=i[1];
    sort(st+1,st+tp+1),tp=unique(st+1,st+tp+1)-st-1;
    fill(tr,tr+tp+1,I);
    auto add=[&](int x,info v) { for(;x;x&=x-1) tr[x]=tr[x]+v; };
    auto qry=[&](int x) { info s=I; for(;x<=tp;x+=x&-x) s=s+tr[x]; return s; };
    for(auto i:Q) {
        if(i[1]>=(V+i[0]-1)/i[0]) ans=min(ans,i[1]);
        int id=lower_bound(st+1,st+tp+1,(V+i[0]-1)/i[0]-i[1]+b[u])-st;
        info z=qry(id);
        ans=min(ans,i[1]+(z.c1==i[2]?z.v2:z.v1)-b[u]);
        id=lower_bound(st+1,st+tp+1,i[1])-st;
        add(id,{i[1],inf,(int)i[2],0});
    }
}
void dfs1(int u) {
    solve(u),vis[u]=true;
    for(int v:G[u]) if(!vis[v]) {
        int rt=0;
        function<void(int,int)> dfs2=[&](int x,int fz) {
            cur[x]=siz[v]-siz[x];
            for(int y:G[x]) if(y!=fz&&!vis[y]) dfs2(y,x),cur[x]=max(cur[x],siz[y]);
            if(!rt||cur[x]<cur[rt]) rt=x;
        };
        dfs2(v,u),dfs1(rt);
    }
}
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>V;
    for(int i=1;i<=n;++i) cin>>a[i]>>b[i];
    for(int i=1,u,v;i<n;++i) cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
    dfs1(1),cout<<ans<<"\n";
    return 0;
}