题目大意：
给一个n个节点的树，然后将其分成k+1个联通块，再在每个联通块取一条路径，将其连接起来，求连接起来的路径最大权值。
题解：
考场只会20分，还都打挂了……
60分的做法其实并不难，nk DP即可，设$f(i,j,0/1/2)$表示i子树选取了j个联通块，i这个节点连了0/1/2条边时的最优解。
100分的做法就是60分做法的拓展。
很容易想到一件事，就是以联通块数为x轴，最优解为y轴，那么这个图像应该是一个单峰上凸函数。同时该离散函数每相邻两点间的斜率是递减的：因为考虑当前联通块数为a，则当联通块数为a+1时，必然是在a时最优解上再连接一段新切出的可空路径并割去一部分可空路径，当补上一条新路径时，我们很容易知道这次补上的路径-割去路径一定小于以前做的同样操作（最优性）。
这样我们发现斜率是具有单调性的（即单调减）。那么我们二分这个斜率，并将原图像减去这个斜率对应的正比例函数，会发现，新图像将会在这个斜率对应点的位置最高，同时也是一个斜率递减函数。
那么我们考虑如何求出此时的答案：新图像上的最高点权值+新图像上最高点联通块数*斜率。
我们考虑这个东西怎么求。
设二元组$f(i,0/1/2)$表示i节点连了0/1/2条边时的最优解和其联通块数（尽量小）。特别的没有连边的i，算为一个联通块，2为0/1/2这三个状态的最优解。
考虑这个东西怎么转移：
假设已经得到子节点v的答案。
对于$f(x,2)$，我们有三种选择，1.保持原来不变，把$f(v,2)$加上；2.由$f(x,1)$和$f(v,1)$合并；3.由$f(x,1)和f(v,0)$合并。
$f(x,1)$,我们同样有三种选择，大体同上者。
$f(x,0)$，我们只有一种选择，即和$f(v,2)$结合。
我们以$f(x,2)$为例：对于第一种情况，联通块数不变直接合并即可，对于第二种情况联通块数减少1，第三种情况同样减少了1个联通块。
得到结果以后比较k+1与最优解对应的联通块数，大于则说明斜率过小，否则说明斜率还可能更大。
代码：
1 #include "bits/stdc++.h" 2 3 using namespace std; 4 5 inline int read(){ 6 int s=0,k=1;char ch=getchar(); 7 while (ch<'0'|ch>'9') ch=='-'?k=-1:0,ch=getchar(); 8 while (ch>47&ch<='9') s=s*10+(ch^48),ch=getchar(); 9 return s*k;10 }11 12 typedef long long ll;13 14 const int N=3e5+10;15 16 struct edges{17 int v,w;edges *last;18 }edge[N<<1],*head[N];int cnt;19 20 inline void push(int u,int v,int w) {21 edge[++cnt]=(edges){v,w,head[u]},head[u]=edge+cnt;22 }23 24 int n,k;25 ll slope;26 const ll inf=1e15;27 28 struct node {29 ll val,num;30 node(){val=num=0;}31 node(ll v,ll nm):val(v),num(nm){}32 inline ll &operator [](int x){33 return x?num:val;34 }35 inline void max(node a){36 if(a[0]>val||(a[0]==val&&a[1] last) if(i->v!=fa) {59 dp(i->v,x);60 f[x][2].add(f[x][2],f[i->v][2]);61 f[x][2].add(f[x][1],f[i->v][1],i->w,1);62 f[x][2].add(f[x][1],f[i->v][0],i->w,0);63 f[x][1].add(f[x][1],f[i->v][2]);64 f[x][1].add(f[x][0],f[i->v][1],i->w,0);65 f[x][1].add(f[x][0],f[i->v][0],i->w,-1);66 f[x][0].add(f[x][0],f[i->v][2]);67 }68 f[x][2].max(f[x][1]);69 f[x][2].max(f[x][0]);70 f[x][2].max(f[x][0].fa());71 }72 73 74 int main(){75 n=read(),k=read()+1;76 for (int i=1;i >1;85 dp(1,0);86 now=f[1][2];87 if(now[1]<=k) 88 ans=now[0]+slope*k,r=slope-1;89 else l=slope+1;90 }91 printf("%lld\n",ans);92 }