【JZOJ5081】【GDSOI2017第三輪模拟】Travel Plan

Description

Data Constraint

Solution

這和以前的一道題很像啊。我們發現 ∑ci 太大了，而 ∑vi 的大小可以接受， 是以我們設出f[i][j]表示目前做到dfs序中第i個物品，選出物品價值和至少為j的最小代價。這可以在O( N∑vi )内解決。然後我們考慮不選某子樹的物品，即在dfs序中有一段物品不選擇。是以我們在處理一個g[i][j]表示與f相同，隻是從後往前做，最後在詢問時，由于f[i]和g[i]單調遞增，是以我們可以打一個指針O( ∑vi )内合并。

Code

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=e3+;
ll f[*maxn],g[maxn/][*maxn],first[maxn],last[maxn],next[maxn],size[maxn],dfn[maxn],v[maxn],c[maxn];
ll n,m,i,t,j,k,l,x,y,z,num,mx,p,num1,d[maxn*25],b1[maxn],ans,ans1[maxn];
struct code{
    ll v,w;
}b[maxn*25],c1[*maxn];
struct code1{
    ll x,y,z;
}q[maxn];
void lian(ll x,ll y){
    last[++num]=y;next[num]=first[x];first[x]=num;
}
void dg(ll x,ll y){
    ll t;dfn[x]=++num;size[x]=;
    for (t=first[x];t;t=next[t]){
        if (last[t]==y) continue;
        dg(last[t],x);size[x]+=size[last[t]];
    }
}
bool cmp(code x,code y){
    return x.w<y.w;
}
bool cmp1(code1 x,code1 y){
    return dfn[x.x]<dfn[y.x];
}
int main(){
    freopen("plan.in","r",stdin);freopen("plan.out","w",stdout);
    scanf("%lld",&n);
    for (i=;i<n;i++)
        scanf("%lld%lld",&x,&y),lian(x,y),lian(y,x);
    for (i=;i<=n;i++)
        scanf("%lld%lld",&v[i],&c[i]),mx=max(mx,v[i]);
    num=;
    dg(,);scanf("%lld",&m);
    for (i=;i<=n;i++)
        b1[dfn[i]]=i;
    memset(f,,sizeof(f));memset(g,,sizeof(g));f[]=;g[n+][]=;p=f[];
    for (i=n;i>=;i--){
        x=v[b1[i]];y=c[b1[i]];
        for (j=mx*n;j>=;j--)
            if (g[i+][j]!=p){
                g[i][j+x]=(g[i+][j]+y<g[i][j+x])?g[i+][j]+y:g[i][j+x];
                g[i][j]=g[i+][j];
            }
        for (j=mx*n-;j>=;j--)
            g[i][j]=(g[i][j+]<g[i][j])?g[i][j+]:g[i][j];
    }
    for (k=;k<=m;k++)
        scanf("%lld%lld",&q[k].x,&q[k].y),q[k].z=k;
    sort(q+,q+m+,cmp1);
    for (k=;k<=m;k++){
        for (i=dfn[q[k-1].x];i<dfn[q[k].x];i++){
            x=v[b1[i]];y=c[b1[i]];
            for (j=mx*n;j>=;j--)
                if (f[j]!=p) f[j+x]=(f[j]+y<f[j+x])?f[j]+y:f[j+x];
            for (j=mx*n-;j>=;j--)
                f[j]=(f[j]<f[j+])?f[j]:f[j+];
        }
        j=mx*n;x=dfn[q[k].x]+size[q[k].x];y=q[k].y;ans=;
        for (i=;i<=mx*n;i++){
            if (f[i]>y) break;
            while (g[x][j]+f[i]>y) j--;
            ans=max(ans,i+j);
        }
        ans1[q[k].z]=ans;
    }
    for (i=;i<=m;i++)
        printf("%lld\n",ans1[i]);
}