题目链接
题解
tu优化!
其实之前做过类似的，思想类似，二分一个价值的偏移量来逼近限制k，大概是clj出的一道集训队胡策啥来着？？
对于本题，问题等价于在树种找出k+1条不想交的链后，使其权值最大
这个DP就好，你就有60分了，可我不知道转化呀qwqqqq
然后发现，对于每个离散的k的最优解，它的的图像是一个上凸包，且斜率严格递降
意会一下，对于价值更优的边直接切了，然后优化他的子结构，这样的价值增量肯定不如上一个更优，当然，切多了把正边也切了（泥萌20分暴力不就这样的打的么qwqqqq
我们可以二分一个直线的斜率，用这个直线去切这个凸包，根据切点的横坐标与k值大小改变斜率
那我们怎么找到切点嘞，实际上就是这个凸包函数减去这条斜率为k的一次函数直线后，的最高点
显然如果相切的话，只有切点是距离切线最近的点
那么我们二分这个斜率，相当于二分一个凸包函数的偏移量
来使得切点的横坐标恰好为k，对于二分后的dp是个就最优性问题啦，就不用记录选了几条边了，直接dp就好了
复杂度(O(nlogn))
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
const int maxn = 300007;
inline int read() {
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
while(c <= '9' && c >= '0')x = x * 10 + c - '0',c = getchar();
return x * f;
}
int n,k;
LL tot = 0;
struct node {
int v,w,next;
}edge[maxn << 1];
int head[maxn],num = 0;
inline void add_edge(int u,int v,int w) { edge[++ num]. v = v,edge[num].w = w;edge[num].next = head[u];head[u] = num; }
LL mid;
struct data {
LL x,y;
data (LL a = 0,LL b = 0) : x(a),y(b) {};
bool operator < (const data &a) const {
if(x == a.x) return y > a.y;
else return x < a.x;
}
data operator + (const data &a) const {
return data(x + a.x,y + a.y);
}
data operator + (int a) {
return data(x + a,y);
}
} dp[3][maxn];
data upd(data a) { return data(a.x - mid,a.y + 1); }
void dfs(int u,int fa) {
dp[2][u] = std:: max(dp[2][u] ,data(-mid,1));
for(int i = head[u]; i;i = edge[i].next) {
int v = edge[i].v;
if(v == fa) continue;
dfs(v,u);
dp[2][u] = std::max(dp[2][u] + dp[0][v],upd(dp[1][u] + dp[1][v] + edge[i].w));
dp[1][u] = std::max(dp[1][u] + dp[0][v],dp[0][u] + dp[1][v] + edge[i].w);
dp[0][u] = dp[0][u] + dp[0][v];
}
dp[0][u] = std::max(dp[0][u],std::max(upd(dp[1][u]),dp[2][u]));
}
int main() {
n = read(); k = read(); k ++;
for(int u,v,w,i = 1;i < n;++ i) {
u = read();v = read(); w = read();
tot += abs(w) ;
add_edge(u,v,w);add_edge(v,u,w);
}
LL l = -tot,r = tot;
while(l <= r) {
mid = l + r >> 1;
memset(dp,0,sizeof dp);
dfs(1,0);
if(dp[0][1].y <= k) r = mid - 1;
else l = mid + 1;
}
memset(dp,0,sizeof dp); mid = l; dfs(1,0); printf("%lld
",l * k + dp[0][1].x);
return 0;
}