假设已经linkcut完了树，答案显然是树的直径。那么考虑这条直径在原树中是怎样的。容易想到其是由原树中恰好k+1条点不相交的链（包括单个点）拼接而成的。因为这样的链显然可以通过linkcut拼接起来，而若选择不超过k条链则可能有链不得不被cut拆开，即使不会被拆开也可以通过选择单点来达到恰好k+1条（下设k=k+1）。

　　那么问题变为在树上选择k条点不相交的链使边权和最大。最简单的dp就是设f[i][j]为i子树中选j条链的最大权值，且用一维012状态记录i这个点在子树中的度数，转移类似于一个树形背包。复杂度看起来是O(nk^2)，实际上似乎是O(nk)，可以拿60分。

　　然而再往上即使复杂度去一个k也没有更高的分了。这暗示我们可以做到与k无关的复杂度。

　　考虑去掉k的限制。这样仍然是一个dp，只是去掉了一维，复杂度变为O(n)。注意一些细节，比如说仅选择单点看做度数为1，按照210的顺序更新等等。

　　k怎么办？考虑wqs二分，也叫凸优化、带权二分啥的。我们把选择x条链的代价设为x*cost。可以发现，如果把cost设成-inf，那么会选择n条链；如果设成inf，会选择0条链；而随着cost从-inf增加到inf，最优链数感觉上应该是单调不增的。那么我们可以二分cost，使得链数最终在k处停止，这个时候肯定求得了选k条链的最优方案，于是再补回cost就可以求得最优解了。至于这个东西是不是单调不增的呢？貌似是的。为什么呢？大胆猜想不用证明感觉一个东西便宜的时候都不买，涨价了更没有理由买啊。证明我也不懂。

　　dp的时候记录一下最优的时候至少需要选择几条链。因为cost可能与一段链数对应，有可能无法刚好二分到选了k条链，不过这说明他们在该情况下都能作为最优解，则他们的加权（x*cost）答案相同。那么只要能够二分到这种加权答案就可以算出来k条链的答案了。于是保留选择的链数最接近k而又不超过k的答案，最终答案加上k*cost。

　　还有一个细节，cost只需要在整数范围内二分就可以了。具体还是用坐标系来理解吧，链数对应的实际答案构成一个凸壳，用斜率为cost的直线去切这个凸壳，第一个碰上的点就是我们找到的答案。因为其中都是整点，用整数的斜率去切就可以了。但其实我也不知道我在说啥。

　　“题目并不难。”

 

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define N 300010#define ll long long#define inf 300000000010#define max(a,b) (((a)>(b))?(a):(b))int n,k,p[N],t=0;ll ans;struct data2{ ll x;int cnt; bool operator >(const data2&a) const { return x>a.x||x==a.x&&cnt
           
            >1; dfs(1,1,mid); if (max(f[1][0],max(f[1][1],f[1][2])).cnt<=k) ans=max(f[1][0],max(f[1][1],f[1][2])).x+k*mid,r=mid-1; else l=mid+1; } cout<