[九省联考2018]林克卡特树(DP+wqs二分)

摘要:
对于k=0和k=1的点,可以直接计算树的直径。然后对于60个点,有一个重要的转换:在树中找到k+1个点不相交链之后,找到最大连续边权重和。因此,我们可以用斜率将凸包切成两半,并根据切点的横坐标和k的大小旋转直线。现在的问题是如何找到最高点。这成为一个优化问题。可以从DP方程中删除一个维度。所以你可以通过,复杂度为$O$。

对于k=0和k=1的点,可以直接求树的直径。

然后对于60分,有一个重要的转化:就是求在树中找出k+1条点不相交的链后的最大连续边权和。

这个DP就好。$O(nk^2)$

然后我们完全不可以想到,将best[k](选择k条链的答案)打表输出,更不可能然后作差分,发现得到的数组是递减的。

这说明:best[k]是一个上凸包。

于是我们可以二分一个斜率去切这个凸包(类似导数),根据切点横坐标与k的大小旋转直线(改变斜率)。

考虑给你一个直线斜率k,怎么找到它和凸包的切点。实际上就相当于将这个凸函数减去y=kx,再求凸包最高点。

感性理解一下,就是相当于在凸包下面画一条直线,然后旋转整个坐标系使这条直线就是x轴,然后正确性就比较显然了。

现在问题就是,如何找到最高点,这成了一个最优性问题,DP方程里可以去掉一维(已选链数不需要记录了)。

这样就可以通过了,复杂度$O(knlog n)$。这又叫WQS二分

https://www.luogu.org/problemnew/solution/P4383

https://blog.csdn.net/izumi_hanako/article/details/80071419

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define rep(i,l,r) for (int i=l; i<=r; i++)
 5 typedef long long ll;
 6 using namespace std;
 7 
 8 const int N=300010;
 9 int n,k,u,v,w,cnt,to[N<<1],nxt[N<<1],val[N<<1],h[N];
10 ll mid,tot;
11 void add(int u,int v,int w){ to[++cnt]=v; val[cnt]=w; nxt[cnt]=h[u]; h[u]=cnt; }
12 struct P{
13     ll x,y;
14     bool operator < (const P &b) const {return x==b.x? y>b.y : x<b.x;}
15     P operator + (const P &b) const {return (P){x+b.x,y+b.y};}
16     P operator + (int b) {return (P){x+b,y};}
17 }dp[3][N];
18 P upd(P a){ return (P){a.x-mid,a.y+1}; }
19 
20 void dfs(int u,int fa){
21     dp[2][u]=max(dp[2][u],(P){-mid,1});
22     for (int i=h[u],v; i; i=nxt[i])
23         if ((v=to[i])!=fa){
24             dfs(v,u);
25             dp[2][u]=max(dp[2][u]+dp[0][v],upd(dp[1][u]+dp[1][v]+val[i]));
26             dp[1][u]=max(dp[1][u]+dp[0][v],dp[0][u]+dp[1][v]+val[i]);
27             dp[0][u]=dp[0][u]+dp[0][v];
28         }
29     dp[0][u]=max(dp[0][u],max(upd(dp[1][u]),dp[2][u]));
30 }
31 
32 int main(){
33     freopen("lct.in","r",stdin);
34     freopen("lct.out","w",stdout);
35     scanf("%d%d",&n,&k); k++;
36     rep(i,2,n) scanf("%d%d%d",&u,&v,&w),tot+=abs(w),add(u,v,w),add(v,u,w);
37     ll L=-tot,R=tot;
38     while (L<=R){
39         mid=(L+R)>>1; memset(dp,0,sizeof(dp)); dfs(1,0);
40         if (dp[0][1].y<=k) R=mid-1; else L=mid+1;
41     }
42     memset(dp,0,sizeof(dp)); mid=L; dfs(1,0); printf("%lld
",L*k+dp[0][1].x);
43     return 0;
44 }

免责声明:文章转载自《[九省联考2018]林克卡特树(DP+wqs二分)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇sdoi2018酱油鸡[COGS2479 &amp;&amp; COGS2639]高维偏序(CDQ分治,bitset)下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章