luogu P4383 [八省联考 2018] 林克卡特树

题面传送门
真是一道大毒瘤题目，写了我两个晚上。
这个题面转化一下就是树上选\(k+1\)条点不相交路径。
首先不难发现有一个\(O(nk)\)的dp：设\(dp_{i,j,0/1/2}\)为\(i\)子树内选了\(j\)条链，当前点度数0/1/2的最大值。随便转移
特别的我们把一个单独的点看作2度数。
然后这个显然是上凸的函数。所以可以WQS二分。
重定义一个pair会比较好写，不过细节仍然很多。
code:

#include
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define RI re int
#define ll long long
#define db double
#define lb long db
#define N 300000
#define K 100
#define mod 1000000007
#define Mod (mod-1)
#define eps (1e-5)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define d(x,y) (m*x+(y))
#define R(n) (rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
using namespace std;
int n,m,k,x,y,z,siz[N+5];ll l,r,mid;const ll INF=1e16;
struct yyy{int to,w,z;};struct ljb{int head,h[N+5];yyy f[N+5<<1];I void add(int x,int y,int z){f[++head]=(yyy){y,z,h[x]};h[x]=head;}}s;
struct Pai{
	ll w;int g;bool operator >(const Pai &B)const{return w^B.w?w>B.w:gk;}
int main(){
	freopen("1.in","r",stdin);
	RI i;Me(F,-0x3f);scanf("%d%d",&n,&k);k++;for(i=1;i>1,(check()?l:r)=mid;mid=r;check();printf("%lld\n",r*k+max(max(F[1][0],F[1][1]),F[1][2]).w);
}