题意
给定一个 $n$ 个点边带权的无根树, 要求切断其中恰好 $k$ 条边再连 $k$ 条边权为 $0$ 的边重新连成一棵树, 最大化新树上某条路径的权值和.
$0\le k<n\le 3\times 10^5$. 边权的绝对值不超过 $1\times 10^6$.
提示: 题目并不难
题解
当时场上做这题的时候根本不知道有wqs二分这种高端套路…看到提示之后果断跑路了qaq…
首先切断 $k$ 条边再连 $k$ 条 $0$ 权边并最大化一条路径的权值和显然相当于最大化在树上选 $k+1$ 条点不相交路径的权值和.
这种恰好选若干条的一般考虑wqs二分. 二分一个附加权值, 每次多选一条链就会多产生一些权值, 然后DP的时候就可以变成 “在树中选若干条链并最大化权值和”. 定义 $dp_{i,0/1/2}$. 为以 $i$ 为根的子树中, $i$ 号点度数为 $0/1/2$ 时的最大权值. 注意单点也可以作为一条合法的链, 我们可以看成一条自环贡献两个度数.
那么分几种情况讨论就好了. 度数小的状态可以通过向子树连一条边的转移到度数大的状态. 注意其中链的数量的增减就好了.
以及wqs二分在DP的时候需要顺便计数, 计数部分用结构体来写会好写很多(而且好像跑得还更快)
还有就是注意在值相等的时候对于链的数量的选择要有侧重. 一般倾向于统一选多的, 然后在二分循环里具体问题具体分析.
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
#include <bits/stdc++.h>
const int MAXV=3e5+10;
const int MAXE=1e6+10;
typedef long long intEx;
const intEx INF=1e15;
struct Edge{
int from;
int to;
int dis;
Edge* next;
};
Edge E[MAXE];
Edge* head[MAXV];
Edge* top=E;
struct Data{
intEx sum;
int cnt;
Data(){}
Data(const intEx& s,int c):sum(s),cnt(c){}
Data friend operator+(const Data& a,const Data& b){
return Data(a.sum+b.sum,a.cnt+b.cnt);
}
Data friend operator-(const Data& a,const Data& b){
return Data(a.sum-b.sum,a.cnt-b.cnt);
}
bool friend operator<(const Data& a,const Data& b){
return a.sum==b.sum?a.cnt<b.cnt:a.sum<b.sum;
}
};
int n;
int k;
Data add;
Data dp[MAXV][3];
void DFS(int,int);
void Insert(int,int,int);
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<n;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
Insert(a,b,c);
Insert(b,a,c);
}
add.cnt=1;
intEx l=-1e12,r=1e12;
while(r-l>1){
intEx mid=(l+r+1)>>1;
add.sum=mid;
DFS(1,0);
Data cur=std::max(dp[1][0],std::max(dp[1][1],dp[1][2]));
if(cur.cnt>=k+1)
r=mid;
else
l=mid;
}
add.sum=r;
DFS(1,0);
Data cur=std::max(dp[1][0],std::max(dp[1][1],dp[1][2]));
printf("%lld\n",cur.sum-(k+1)*r);
return 0;
}
void DFS(int root,int prt){
dp[root][0]=Data(0,0);
dp[root][1]=Data(-INF,0);
dp[root][2]=add;
for(Edge* i=head[root];i!=NULL;i=i->next){
if(i->to!=prt){
DFS(i->to,root);
Data mx=std::max(dp[i->to][0],std::max(dp[i->to][1],dp[i->to][2]));
dp[root][2]=std::max(dp[root][2]+mx,dp[root][1]+Data(i->dis,0)+std::max(dp[i->to][0],dp[i->to][1]-add));
Data tmp=dp[root][0]+Data(i->dis,0)+std::max(dp[i->to][0]+add,dp[i->to][1]);
dp[root][1]=std::max(dp[root][1]+mx,tmp);
dp[root][0]=dp[root][0]+mx;
}
}
}
inline void Insert(int from,int to,int dis){
top->from=from;
top->to=to;
top->dis=dis;
top->next=head[from];
head[from]=top++;
}
|
