【jzoj5248】【NOIP2017提高A组模拟8.10】【花花的聚会】【动态规划】【可持久化线段树】

题目大意

解题思路

设f[i]表示i到根最小花费，用可持久化线段树维护到根的路径上的f，区间求最小值即可。

code

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LF double
#define LL long long
#define ULL unsigned int
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j) for(int i=begin[j];i;i=next[i])
#define f2(i,j) for(int i=begi2[j];i;i=nex2[i])
using namespace std;
int const mn=1e5+9,inf=1e9+7;
int n,m,q,gra,gr2,pon,begin[mn],begi2[mn],to[mn],next[mn],tim[mn],
    cost[mn],nex2[mn],f[mn],mi[mn*20],son[mn*20][2];
void insert(int u,int v){
    to[++gra]=v;
    next[gra]=begin[u];
    begin[u]=gra;
}
void inser2(int v,int k,int w){
    tim[++gr2]=k;
    cost[gr2]=w;
    nex2[gr2]=begi2[v];
    begi2[v]=gr2;
}
int min(int x,int y){
return (x<y)?x:y;
}
int max(int x,int y){
return (x>y)?x:y;
}
int qury(int p,int l,int r,int u,int v){
int md=(l+r)/2;
if((l==u)&&(r==v))return mi[p];
if(v<=md)return qury(son[p][0],l,md,u,v);
else if(md<u)return qury(son[p][1],md+1,r,u,v);
else return min(qury(son[p][0],l,md,u,md),qury(son[p][1],md+1,r,md+1,v));
}
void oper(int p,int q,int l,int r,int u,int v){
int md=(l+r)/2;
if(l==r){
        mi[p]=v;
return;
    }
if(u<=md){
        son[p][1]=son[q][1];
        oper(son[p][0]=++pon,son[q][0],l,md,u,v);
    }else if(md<u){
        son[p][0]=son[q][0];
        oper(son[p][1]=++pon,son[q][1],md+1,r,u,v);
    }
    mi[p]=min(mi[son[p][0]],mi[son[p][1]]);
}
void dfs(int p,int q,int dep){
if(q)f2(i,p)f[p]=min(f[p],qury(q,1,n,max(dep-tim[i],1),dep-1)+cost[i]);
    oper(p,q,1,n,dep,f[p]);
    fr(i,p)dfs(to[i],p,dep+1);
}
int main(){
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
scanf("%d%d",&n,&m);
    fo(i,1,n-1){
int u,v;
scanf("%d%d",&u,&v);
        insert(v,u);
    }
    fo(i,1,m){
int v,k,w;
scanf("%d%d%d",&v,&k,&w);
        inser2(v,k,w);
    }
    pon=n;
    mi[0]=inf;
    fo(i,2,n)f[i]=inf;
    dfs(1,0,1);
scanf("%d",&q);
    fo(i,1,q){
int x;
scanf("%d",&x);
printf("%d\n",f[x]);
    }
return 0;
}