【HDOJ5956】The Elder（树形DP，斜率优化）

题意：有一棵n个点的有根树，每条边上有一个边权。给定P，从i跳到它的祖先j的费用是距离的平方+P，问所有点中到根节点1的总花费最大值

n<=1e5,p<=1e6,w<=1e2

思路：对于根节点到每个点i的路径上是一个下凸壳，是经典的斜率优化

考虑在dfs时维护这个下凸壳，在斜率优化加入与删除点时记录下时间戳和操作的类型，dfs结束时恢复即可

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 typedef long long ll;

 using namespace std;

 #define N   210000

 #define oo  10000000

 #define MOD 1000000007

 struct node

 {

     int t,x,y;

 }stk[N];

 ll dp[N],s[N],P;

 int dep[N],head[N],vet[N],nxt[N],len[N],q[N],flag[N],n,top,tot,tim,t,w;

 int add(int a,int b,int c)

 {

     nxt[++tot]=head[a];

     vet[tot]=b;

     len[tot]=c;

     head[a]=tot;

 }

 ll sqr(ll x)

 {

     return x*x;

 }

 ll calc(int i,int j)

 {

     return dp[j]+sqr(s[i]-s[j])+P;

 }

 int cmp(int x,int y,int z)

 {

     ll x1=dp[x]-dp[y]+sqr(s[x])-sqr(s[y]);

     ll y1=s[x]-s[y];

     ll x2=dp[y]-dp[z]+sqr(s[y])-sqr(s[z]);

     ll y2=s[y]-s[z];

     return x1*y2>=x2*y1;

 }

 void dfs(int u)

 {

     tim++;

     flag[u]=;

     if(u==)

     {

         t=; w=; dp[u]=-P; q[]=;

     }

      else

      {

          while(t<w&&calc(u,q[t])>=calc(u,q[t+]))

         {

             stk[++top].t=tim; stk[top].x=; stk[top].y=q[t];

             t++;

         }

         dp[u]=calc(u,q[t]);

         while(t<w&&cmp(q[w-],q[w],u))

         {

             stk[++top].t=tim; stk[top].x=; stk[top].y=q[w];

             w--;

         }

         q[++w]=u;

         stk[++top].t=tim; stk[top].x=;

     }

     int tmp=tim;

     int e=head[u];

     while(e)

     {

         int v=vet[e];

         if(!flag[v])

         {

             s[v]=s[u]+len[e];

             dfs(v);

         }

         e=nxt[e];

     }

     while(stk[top].t==tmp)

     {

         if(stk[top].x==) q[--t]=stk[top].y;

         if(stk[top].x==) q[++w]=stk[top].y;

         if(stk[top].x==) w--;

         top--;

     }

 }

 int main()

 {

     int cas;

     scanf("%d",&cas);

     while(cas--)

     {

         int n;

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

         s[]=;

         tot=;

         for(int i=;i<=n;i++) head[i]=flag[i]=;

         for(int i=;i<=n-;i++)

         {

             int x,y,z;

             scanf("%d%d%d",&x,&y,&z);

             add(x,y,z);

             add(y,x,z);

         }

         tim=;

         t=; w=; top=;

         dfs();

         ll ans=;

         for(int i=;i<=n;i++) ans=max(ans,dp[i]);

         printf("%I64d\n",ans);

     }

     return ;

 }

巴特西

【HDOJ5956】The Elder（树形DP，斜率优化）

最新文章

热门文章