BZOJ 3672[Noi 2014]티켓 팅(숙련 분할+볼록 케이스 유지)

제목 링크:http://www.lydsy.com:808/JudgeOnline/problem.php?id=3672
제목:뿌리 가 있 는 나무 한 그루(1 은 뿌리)를 주 고 가장자리 에 길이 가 있다.각 점 u 는 세 개의 속성(len[u],p[u],q[u])이 있 습 니 다.매번 u 는 u 의 특정한 조상 노드 v(v 만족 dist(u,v)<=len[u])로 옮 길 수 있 고 대 가 는 p[u]*dist(u,v)+q[u]입 니 다.점 마다 1 로 옮 기 는 대 가 를 구하 다.
사고:먼저 f[u]를 설정 하여 u 가 1 로 이전 하 는 최소 대 가 를 나타 낸다.그러면 우 리 는 DP 방정식 을 얻 을 수 있다.f[u]=min(f[v]+p[u]*(s[u]-s[v])+q[u](v 는 u 의 조상 노드 이 고 s[u]는 u 에서 뿌리 노드 1 까지 의 거 리 를 나타 내 며 s[u]-s[v]<=len[u]).
위의 식 을 f[u]=(-s[v]*p[u]+f[v])+(s[u]*p[u]+q[u])로 변형 합 니 다.그 중에서 s[u]*p[u]+q[u]는 u 를 정격 치 로 한다 면 우 리 는-s[v]*p[u]+f[v]의 최소 치 만 요구 하면 된다.
우 리 는 깊이 가 작은 것 에서 큰 것 까지 순서대로 계산한다.그러면 u 를 계산 할 때 그의 모든 조상 노드 는 이미 계산 되 었 고 그들의 f[v]와 s[v]값 은 이미 알 고 있다.그렇다면 우 리 는 u 의 모든 조상 을 하나하나 열거 할 수 없다.그래서 어떻게 지 킬 것 인가?k=-s[v],b=f[v],x=p[u],y=kx+b 를 설정 합 니 다.우 리 는 지금 Y 의 최소 값,k<0,경사 율 k,y 축 절 거 리 를 구 합 니 다.우 리 는[1,fa[u]이 점 들 로 구 성 된 상 철 각 만 유지 하면 된다 는 것 을 발견 했다.
우 리 는 현재 이미 위의 돌출 껍질 을 지 켰 다.지금 은 점(-s[t],f[t])을 추가 했다.우 리 는 제목 의 가장자리 거리 가 0 보다 엄격 하기 때문에 이 s[t]는 엄 격 히 증가 하 는 것 을 발견 했다.즉,경사 율 이 점점 마이너스 에 가 까 워 지 는 것 이다.그래서...우 리 는 먼저 그것 을 이미 유지 한 볼록 케이스 의 마지막 에 넣 으 면 된다.이때 앞 에 더 이상 최 우수 치가 아 닐 수도 있 습 니 다.우 리 는 순서대로 뒤에서 판단 하면 최 우수 치가 아니면 삭제 할 수 있 습 니 다.따라서 하나의 vector 로 유지 하면 됩 니 다(splay,set 같은 것 을 사용 하지 않 아 도 됩 니 다).
그래서 우 리 는 알고리즘 을 얻 었 다.
(1)우선,트 리 체인 을 나 누고 선분 트 리 로 모든 체인 을 유지 하 며 선분 트 리 의 각 노드 는 하나의 vector 로 이 구간 의 점 으로 구 성 된 돌출 각 을 유지 합 니 다.
(2)깊이 에 따라 작은 것 부터 큰 것 까지 순서대로 계산한다.여기에 거리 제한 이 있 기 때문에 u 에 대해 마지막 으로 우리 가 조회 해 야 할 것 은 구간[v,fa[u],v 는 s[u]-s[v]<=len[u]의 깊이 를 만족 시 키 는 가장 작은 u 의 조상 이다.
(3)노드 u 를 계산 한 후 이 점 을 포함 하 는 모든 구간 에 삽입 합 니 다.

const i64 inf=(1LL<<62);

const int mod=1000000007;

const int N=200005;

  

  

  

vector<int > g[N];

int n,t;

int fa[N];

i64 len[N],p[N],q[N],dis[N];

  

int sonNum[N];

int dep[N];

  

i64 s[N];

  

void DFS(int u)

{

    sonNum[u]=1;

    int i;

    for(i=0;i<SZ(g[u]);i++)

    {

        int v=g[u][i];

        dep[v]=dep[u]+1;

        s[v]=s[u]+dis[v];

        DFS(v);

        sonNum[u]+=sonNum[v];

    }

}

  

  

int id,belong[N],pos[N],mp[N];

  

  

void dfs(int u,int root)

{

    id++;

    belong[u]=root;

    pos[u]=id;

    mp[id]=u;

    int i,k=n+1;

    for(i=0;i<SZ(g[u]);i++) if(sonNum[k]<sonNum[g[u][i]]) k=g[u][i];

    if(k==n+1) return;

    dfs(k,root);

    for(i=0;i<SZ(g[u]);i++)

    {

        if(g[u][i]!=k) dfs(g[u][i],g[u][i]);

    }

}

  

  

struct node

{

    int L,R;

    vector<pair<i64,i64> > root;

};

  

  

node A[N<<2];

  

void build(int t,int L,int R)

{

    A[t].L=L;

    A[t].R=R;

    A[t].root.clear();

    if(L==R)

    {

        return;

    }

    int M=(L+R)>>1;

    build(t<<1,L,M);

    build(t<<1|1,M+1,R);

}

  

#define pdd pair<i64,i64>

  

i64 f[N];

  

double cross(pdd a,pdd b)

{

    return 1.0*(a.second-b.second)/(b.first-a.first);

}

  



int sgn(double x)

{

	if(x>1e-20) return 1;

	if(x<-1e-20) return -1;

	return 0;

}



void add(vector<pair<i64,i64> > &x,i64 s,i64 f)

{

    pdd p3=MP(s,f);

    while(SZ(x)>=2)

    {

        pdd p2=x[SZ(x)-1];

        pdd p1=x[SZ(x)-2];

        double x1=cross(p2,p3);

        double x2=cross(p1,p3);

        if(sgn(x1-x2)==1) break;

        x.pop_back();

    }

	if(SZ(x)==1&&f<=x[0].second)  x.pop_back();

    x.pb(p3);

}

  

void add(int t,int pos,i64 s,i64 f)

{

    add(A[t].root,s,f);

    if(A[t].L==A[t].R) return;

    int M=(A[t].L+A[t].R)>>1;

    if(pos<=M) add(t<<1,pos,s,f);

    else add(t<<1|1,pos,s,f);

}

  

i64 curX;

  

i64 get(vector<pdd> x)

{

    int L=0,R=SZ(x)-1;

    while(R-L>=4)

    {

        int M=(R+L)>>1;

        double xx=cross(x[M-1],x[M]);

        if(sgn(xx-curX)>=0) R=M;

        else L=M;

    }

    i64 ans=inf;

    int i;

    for(i=L;i<=R;i++)

    {

        pdd p=x[i];

        i64 tmp=curX*p.first+p.second;

        if(tmp<ans) ans=tmp;

    }

    return ans;

}

  

i64 cal(int t,int L,int R,i64 len)

{

    if(A[t].L==L&&A[t].R==R)

    {

        int u1=mp[L];

        int u2=mp[R];

        if(s[u2]-s[u1]<=len) return get(A[t].root);



        int M=(A[t].L+A[t].R)>>1;

        i64 ans=cal(t<<1|1,M+1,R,len);

        u1=mp[A[t<<1].R];

        len-=(s[u2]-s[u1]);

        if(len<0) return ans;

        i64 tmp=cal(t<<1,L,M,len);

        if(tmp<ans) ans=tmp;

        return ans;

    }

    else

    {

        int M=(A[t].L+A[t].R)>>1;

        if(R<=M) return cal(t<<1,L,R,len);

        if(L>M) return cal(t<<1|1,L,R,len);

        i64 ans=cal(t<<1|1,M+1,R,len);

        int u1=mp[A[t<<1].R];

        int u2=mp[R];

        len-=(s[u2]-s[u1]);

        if(len<0) return ans;

  

        i64 tmp=cal(t<<1,L,M,len);

        if(tmp<ans) ans=tmp;

        return ans;

    }

}

  

i64 cal(int u)

{

    curX=p[u];

    i64 L=len[u];

    i64 ans=inf;

    while(L>=0)

    {

        i64 tmp=cal(1,pos[belong[u]],pos[u],L);

        if(tmp<ans) ans=tmp;

        if(fa[belong[u]]==0) break;

        L-=(s[u]-s[fa[belong[u]]]);

		u=fa[belong[u]];

    }

    return ans;

}

  

int main()

{

    scanf("%d%d",&n,&t);

    int i;

    for(i=2;i<=n;i++)

    {

        scanf("%d%lld%lld%lld%lld",&fa[i],&dis[i],&p[i],&q[i],&len[i]);

        g[fa[i]].pb(i);

    }

    DFS(1);

    dfs(1,1);

    build(1,1,n);

    add(1,pos[1],0,0);

    for(i=2;i<=n;i++)

    {

        int u=mp[i];

        f[u]=cal(u)+p[u]*s[u]+q[u];

        add(1,pos[u],-s[u],f[u]);

    }

    for(i=2;i<=n;i++) printf("%lld
",f[i]);

}