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

emm感觉其他题解都没有讲的特别清楚。写一篇讲的比较详细的吧。 带权二分，又叫wqs二分/dp凸优化，用于解决一类有固定数量限制的最优化问题。 例如，给你$n$个物品，给定以某些方式选择能得到某些收益/付出某些代价，问选择**恰好**$k$个物品所能得到的最大收益/付出的最小费用。 因为有了$k$的限制，一般来说只能够类似于$f[i][j]$表示前$i$个物品中选择了$j$个时的最优解这样的类似背包的方法来求解。而且这个dp看起来很难优化，因为状态数几乎是满的，而即使能够$O(1)$转移，最多也只能做到$2D/0D$，复杂度为$O(nk)$ 但是，带权二分能够成为这类问题的一个突破口。令$f(x)$表示选择恰好$x$件物品的最优解，如果$f(x)$是一个**凸函数**，我们就能使用带权二分来优化它。 具体而言，对于$x\in[0, n]$，对应的$f(x)$在以$x$为横坐标，$f(x)$为纵坐标的二维平面内构成了一个凸包。 [](http://www.tzr.me/image/QIbe) >一个凸包的示例 我们要求的是$f(k)$，也就是凸包上的一个点$P(k, f(k))$。这个凸包不能直接下手去求，因为时间复杂度无法承受。 考虑引一条固定斜率的直线去切这个凸包，也就是从上向下平移找到最早相交的那个点，这个切点的坐标是可以求出来的(将在后文详细叙述)。也就是说我们能够**确定**凸包上的一个点$Q(x, f(x))$，并且，我们还能确定**这个点在所求$P$点的左侧还是右侧**。 [](http://www.tzr.me/image/QdeX) >引一条直线切凸包 如果$Q$在$P$的左侧，我们减小直线斜率继续尝试，否则增大直线斜率，直到正好切到$P$点。因为是一个凸函数，增大直线斜率后所得切点一定在$Q$左侧，反之亦然。 这样，我们可以通过二分直线斜率的方式来求得$P$点坐标，也求出对应的$f(k)$ [](http://www.tzr.me/image/QmXy) >黄绿红三条直线斜率依次减小，所得切点横坐标依次增大 到了现在，我们唯一需要解决的问题就是怎么找到切点坐标。 设该直线斜率为$m$，解析式为$y=mx+b$,显然要找到最高的切点就需要最大化直线的截距，也就是$b$。 在图像上，我们可以将凸包上的每个点$(x, f(x))$都向下平移至$(x, f(x)-mx)$，不难发现此时这仍是个凸包。此时凸包的最高点即是向下平移后的切点，证明如下： 设切点坐标为$x$ $\because f(x)=mx+b$ $\therefore f(x)-mx=b$ $\therefore \max(b)=\max(f(x)-mx)$ 在切到了$P$点之后，按照上面的方式找到的其实是平移后的$P$点，将它向上平移还原即可。 对应到给定的题目中，只需要把每个物品的收益减去二分的斜率$m$，这样就能保证每多选取一个物品都需付出$m$的代价，然后不考虑$k$的限制求得最大收益$w$，并且求得在得到最大收益的情况下选取的物品个数$c$，则我们求得上述的$Q(c, w+cm)$，根据$c$和限制$k$的大小关系调整直线斜率继续二分即可。 回到本题，显然题目可以转化为选取$k+1$条路径的长度和的最大值。设$f(x)$为选取$x$条路径所得到的最优方案。出题人告诉我们这个$f(x)$是凸的，使用上述的二分方法，二分斜率$m$,令每选取一条路径都需要付出$m$的代价($m$可能为负数)，求此时选任意条路径所能得到的最大收益以及得到最大收益的前提下选取的**最大**路径条数，并按照上面的方法调整斜率即可。 稍有不同的是，我们这里需要找到的是最小的可以使得选取的路径条数$\geq k$的斜率$m$，这也是为何需要选取尽量多的路径。 至于如何求出选取$k+1$条路径的长度和的最大值，可以使用树形dp在$O(n)$的时间里解决。 $f[i][j] (j\in \{0, 1, 2\})$ 表示点$i$的度数为$j$时$i$的子树中的最优解，使用背包转移即可。在具体实现中，背包这一维可以滚掉。 另外还有一些边界和细节问题，这里就不在赘述了，可以参考其他题解或者理解后自行推导。 ```cpp #include <bits/stdc++.h> #define maxn 300005 #define ll long long const int inf=1e13; struct edge { int v, w, next; }edges[maxn<<1]; int n, k, tail=0, u, v, w, cnt, head[maxn]={0}; ll sum,delta,l,r=0,ans; void add_edge(int u, int v, int w) { edges[++tail].v=v; edges[tail].w=w; edges[tail].next=head[u]; head[u]=tail; } struct data{ int c; ll v; data operator + (data d) {data a;a.v=v+d.v;a.c=c+d.c;return a;} bool operator < (data d) {return v<d.v||(v==d.v&&c<d.c);} }dp[maxn][3], temp[3]; data dat(ll v, int c) {data d;d.v=v;d.c=c;return d;} data max(data a, data b) { if (a<b) return b; return a; } void dfs(int u, int f) { for (int i=head[u];i;i=edges[i].next) { int v=edges[i].v; if (v==f) continue; dfs(v, u); dp[u][2]=max(dp[u][2]+dp[v][0], dp[u][1]+dp[v][1]+dat(edges[i].w-delta, 1)); dp[u][1]=max(dp[u][0]+dp[v][1]+dat(edges[i].w, 0), dp[u][1]+dp[v][0]); dp[u][0]=dp[u][0]+dp[v][0]; }dp[u][0]=max(dp[u][0], max(dp[u][1]+dat(-delta, 1), dp[u][2])); } void check(ll x) { delta=x; for (int i=1;i<=n;++i) { dp[i][0]=dat(0, 0);dp[i][2]=dat(-delta, 1); dp[i][1]=dat(0, 0); } dfs(1, 0); sum=dp[1][0].v; cnt=dp[1][0].c; } int main() { scanf("%d %d", &n, &k);k++; for (int i=1;i<n;++i) { scanf("%d %d %d",&u,&v,&w); add_edge(u,v,w);add_edge(v,u,w); r+=(w>0)?w:-w; } l=-r; while (l<=r) { ll mid=(l+r)>>1; check(mid); if (cnt>=k) {l=mid+1; ans=mid;} else r=mid-1; }check(ans); printf("%lld", sum+k*ans); return 0; } ``` wqs的论文:http://www.doc88.com/p-949564862405.html 最后，关于本题$f(x)$为什么是凸的，我翻看了很多篇博客，暂时未发现任何关于它的证明。如果有会证的dalao还烦请赐教。