题解 P4383 【[八省联考2018]林克卡特树lct】

ysner · 2018-04-11 23:07:25 · 题解

给一颗有负边的树，询问在经过k次割边与任意连上边权为0的边后，链上边权最大和。

此题看起来甚火，正解不敢想象，于是先yy一波部分分

• 对于10% 的数据，k = 0 ;
• 对于另外10% 的数据，k = 1 ;
• 对于另外15% 的数据，k = 2 ;
• 对于另外25% 的数据，k \leq 100 ;

10pts算法(k\leq0)

树的直径

20pts算法(k\leq1)

枚举割哪条边，分别给割后产生的两颗树算直径，加起来即可

送分结束

35pts算法(k\leq2)

看来是分类讨论啊，然而并不知道应如何讨论（请求大佬的指教QAQ)

60pts算法(k\leq100)

分类讨论到此为止啦，显然只有树形DP才做的动。。。

任意连上边权为0的边？？？这是什么操作？？？这边有意义吗？？？

看来没有啊，那就把它忽略掉吧。

于是，问题就变成了最大化k+1条不相交的链的链上边权总和

经典树形DP。

设状态f[0/1/2][u][k]表示以u为根的子树（且u的度数为0/1/2）中，选k条链的最优解。

顺便加个大前提：强制每个点对应其父边。

我们可以列出几个状态转移方程式：(v是u的儿子)(i,j\in(0,k))

• 当u点度数为0时，说明这个点不在链上，于是直接合并一下子树里的最优解即可。

  f[0][u][i]=max(f[0][u][i],f[0][u][j]+f[0][v][i-j]);

• 当u点度数为1时，说明这个点是一条链的端点，我们分 自己本身有一条链 和 儿子有一条链 两种情况取大即可，若自己本来不在链上，要加上边权。

  f[1][u][i]=max(f[1][u][i],max(f[0][u][j]+f[1][v][i-j]+e[i].w,f[1][u][o]+f[0][v][i-j]));

• 当u点度数为2时，说明这个点在一条链中间，我们可以认为这种情况是因 自己和儿子都是一条链的端点 或 自己本来就在一条链中间 而形成的，注意此时第一种情况由于连上当前父子之间的边而多了一条链和一个边权。

  f[2][u][i]=max(f[2][u][i],max(f[1][u][j]+f[1][v][i-j-1]+e[i].w,f[2][u][j]+f[0][v][i-j]));

• 还有边界情况（调代码时调出的锅）

• 最后合并答案

  f[0][u][i]=max(f[0][u][i],max(f[1][u][i-1],f[2][u][i]));

答案就是f[0][1][k]

il void dfs(re int u,re int fa)
{
  f[0][u][0]=f[1][u][0]=f[2][u][0]=0;
  for(re int i=h[u];i+1;i=e[i].next)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      dfs(v,u);
      fq(j,k,1)
    {
      f[1][u][j]=max(f[1][u][j],f[0][u][j]+f[1][v][0]+e[i].w);
    fq(o,j-1,0)
    {
      f[0][u][j]=max(f[0][u][j],f[0][u][o]+f[0][v][j-o]);
      f[1][u][j]=max(f[1][u][j],max(f[0][u][o]+f[1][v][j-o]+e[i].w,f[1][u][o]+f[0][v][j-o]));
      f[2][u][j]=max(f[2][u][j],max(f[1][u][o]+f[1][v][j-o-1]+e[i].w,f[2][u][o]+f[0][v][j-o]));
    }
    }
      f[1][u][0]=max(f[1][u][0],f[1][v][0]+e[i].w);
    }
  f[0][u][1]=max(0,f[0][u][1]);
  fp(i,1,k) f[0][u][i]=max(f[0][u][i],max(f[1][u][i-1],f[2][u][i]));
}
int main()
{
  memset(h,-1,sizeof(h));
  n=gi();k=gi();
  fp(i,1,n-1)
    {
      re int u=gi(),v=gi(),w=gi();
      add(u,v,w);add(v,u,w);
    }
  memset(f,-63,sizeof(f));
  k++;dfs(1,0);
  printf("%d\n",f[0][1][k]);
  return 0;
}

*100pts算法($k\leq310^5$)**

辛辛苦苦想出的树形DP废了。。。

假如你是个秒出60pts的巨佬，即将AK之时闲来无事输出选了k条链的最优解，你就会发现：最优解数组是一个上凸函数！！！

这个函数以k的值为x轴，以最优解为y轴。

我们想找到的点，就是(k,best[k])。

于是考虑用一条直线去切这个函数，由此我们可以枚举一个斜率，用60分的DP思想来算出切点。（这好像是个套路?)

算出切点后，我们可以根据切点在k的左右，来缩小斜率范围。

二分？于是复杂度降到O(nlogn)，皆大欢喜。

struct dat
{
    ll x,y;
    il bool operator < (const dat &o) const {return x==o.x? y>o.y : x<o.x;}
    il dat operator + (const dat &o) const {return (dat){x+o.x,y+o.y};}
    il dat operator + (re int o) {return (dat){x+o,y};}
}dp[3][N];
il dat upd(dat o){return (dat){o.x-mid,o.y+1};}
il void dfs(re int u,re int fa)
{
    dp[2][u]=max(dp[2][u],(dat){-mid,1});
    for(re int i=h[u];i+1;i=e[i].next)
    {
        re int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u);
        dp[2][u]=max(dp[2][u]+dp[0][v],upd(dp[1][u]+dp[1][v]+e[i].w));
        dp[1][u]=max(dp[1][u]+dp[0][v],dp[0][u]+dp[1][v]+e[i].w);
        dp[0][u]=dp[0][u]+dp[0][v];
    }
    dp[0][u]=max(dp[0][u],max(upd(dp[1][u]),dp[2][u]));
}
int main()
{
    memset(h,-1,sizeof(h));
  n=gi();k=gi();++k;
  fp(i,1,n-1)
  {
     re int u=gi(),v=gi(),w=gi();tot+=abs(w);
     add(u,v,w);add(v,u,w);
  }
  l=-tot,r=tot;
  while(l<=r)
  {
      mid=l+r>>1;
      memset(dp,0,sizeof(dp));
      dfs(1,0);
      if(dp[0][1].y<=k) r=mid-1;
      else l=mid+1;
  }
  memset(dp,0,sizeof(dp));
  mid=l;dfs(1,0);
  printf("%lld\n",l*k+dp[0][1].x);
  return 0;
}