【BZOJ5252】林克卡特树（动态规划，凸优化）

题面

题解

这个东西显然是随着断开的越来越多，收益增长速度渐渐放慢。

所以可以凸优化。

考虑一个和\(k\)相关的\(dp\)

这个题目可以转换为在树上选择\(K\)条不相交的路径。

设\(f[i][0/1/2]\)表示当前点\(i\)，这个点不和父亲连/和父亲连/在这里将两条链合并的最优值。

再记一维\(k\)，表示子树中已经选了\(k\)条链。

这样子可以直接转移。

那么凸优化\(dp\)，再额外记录一下最优解的链的最小值，就好了。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define ll long long#define MAX 300300inline int read(){ int x=0;bool t=false;char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=true,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return t?-x:x;}struct Line{int v,next,w;}e[MAX<<1];int h[MAX],cnt=1;inline void Add(int u,int v,int w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}ll sum;int n,K;struct Node{ll x;int y;}f[3][MAX],ans;bool operator<(Node a,Node b){if(a.x!=b.x)return a.x
          
           b.y;}Node operator+(Node a,Node b){return (Node){a.x+b.x,a.y+b.y};}void cmax(Node &a,Node b){a=a
           
            >1; ans=(Node){-1ll<<60,0};dfs(1,0,mid); if(ans.y>K)l=mid+1; else r=mid; } ans=(Node){-1ll<<60,0};dfs(1,0,r); printf("%lld\n",r*K+ans.x); return 0;}