个人博客地址：[blog.jerryhzy.top](blog.jerryhzy.top)↵
↵
比赛链接 [contest:1901]↵
↵
目前进度：↵
↵
| A | B | C | D | E | F |↵
| :------------: | :------------: | :------------: | :------------: | :----------: | :--------: |↵
| solved contest | solved contest | solved contest | solved contest | solved later | not solved |↵
↵
↵
↵
## A. Line Trip↵
↵
### 简要翻译↵
↵
在一维数轴上，有一辆车，刚开始在 $0$ 且油箱为满，走一个单位消耗一升油，经过 $a_1,a_2\ldots a_n$ 处可加满油。↵
↵
现在需要从 $0$ 走到 $x$ 再走回 $0$，求能完成路径的油箱油量最小值。↵
↵
### 思路解析↵
↵
先不考虑回程，设 $a_0=0$，则 $ans = \underset{1\le i\le n}{max} \lbrace a_{i}-a_{i-1} \rbrace$。↵
↵
在 $x$ 处转弯时不能加油，所以有 $ans = max(ans,2(x-a_n))$。↵
↵
返程和去程一样，不用再统计。↵
↵
### 代码↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include<algorithm>↵
#include<iostream>↵
const int N=100;↵
int a[N],n,x;↵
void work(){↵
std::cin>>n>>x;↵
for(int i=1;i<=n;++i)↵
std::cin>>a[i];↵
int ans=2*(x-a[n]);↵
for(int i=1;i<=n;++i)↵
ans=std::max(ans,a[i]-a[i-1]);↵
std::cout<<ans<<std::endl;↵
}↵
signed main(int argc,char **argv){↵
// freopen("order.in","r",stdin);↵
// freopen("order.out","w",stdout);↵
std::cin.tie(nullptr)->sync_with_stdio(false);↵
int T;↵
std::cin>>T;↵
while(T--)↵
work();↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
## B. Chip and Ribbon↵
↵
### 简要翻译↵
↵
有一列 $n$ 个格子和一个指针，一开始格子里的数 $a_i=0$ 。↵
↵
第 $1$ 步，Mococarp 会把指针放在第一个格子上，接下来每一步可以做下列两种移动之一：↵
↵
1. 若指针在第 $i$ 个格子上，且 $i \neq n$，则将指针放在 $i+1$ 上。↵
↵
2. 将指针放在任意一个格子上（可以放在同一个格子上）。↵
↵
每一步之后，若指针在第 $x$ 个格子上，则 $a_x$ 加一。↵
↵
现在，Mococarp 想尽可能少的使用移动 $2$，使得 $\forall i\in [1,n],a_i=c_i$。↵
↵
### 思路解析↵
↵
只使用移动 $1$ 时相当于给一个区间加一，问题转化为用多少个区间可以使 $i$ 被 $c_i$ 个区间包含。↵
↵
那么 $c_i>c_{i-1}$ 时表示有 $c_i -c_{i-1}$ 个区间要从 $i$ 开始，$ans+=c_i-c_{i-1}$。↵
↵
### 代码↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include<algorithm>↵
#include<iostream>↵
#include<vector>↵
using std::cin;↵
using std::cout;↵
using std::endl;↵
using std::vector;↵
typedef long long ll;↵
const int N = 200010;↵
ll c[N],n;↵
void work(){↵
cin>>n;↵
for(int i=1;i<=n;++i)↵
cin>>c[i];↵
ll ans=0;↵
for(int i=1;i<=n;++i)↵
if(c[i]>c[i-1])↵
ans+=c[i]-c[i-1];↵
cout<<ans-1<<endl;↵
}↵
signed main(int argc,char **argv){↵
// freopen("order.in","r",stdin);↵
// freopen("order.out","w",stdout);↵
cin.tie(nullptr)->sync_with_stdio(false);↵
int T;↵
cin>>T;↵
while(T--)↵
work();↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
## C. Add, Divide and Floor↵
↵
### 简要翻译↵
↵
有一个数组 $\lbrace a_n \rbrace$，每次可以选一个 $x$，将所有 $a_i$ 赋值为 $\lfloor \dfrac{a_i+x}{2} \rfloor$，求最少次数使 $a_1=a_2=\cdots=a_n$。↵
↵
### 思路解析↵
↵
先考虑两个数 $x,y(x<y)$ 如何化为相等值。↵
↵
考虑两者的差值，若选的数 $v \ge 2$ 则总有等效操作。↵
↵
如果 $v\ge 2$ 且为偶数，则 $\lfloor \dfrac{x+v}{2} \rfloor = \lfloor \dfrac{x}{2} \rfloor+\dfrac{v}{2}$，$\lfloor \dfrac{y+v}{2} \rfloor = \lfloor \dfrac{y}{2} \rfloor+\dfrac{v}{2}$，和直接除以二的效果相同。↵
↵
如果 $v\ge 2$ 且为奇数，则和加一再除以二的效果相同。↵
↵
观察样例，在 $x$ 为奇数 且 $y$ 为偶数时，加一再除以二相当于除以二后只给 $x$ 加一。↵
↵
其他情况下，加一再除以二不如直接除以二。↵
↵
因为 $x\le y \Leftrightarrow \lfloor \dfrac{x+v}{2} \rfloor \le \lfloor \dfrac{y+v}{2} \rfloor$，所以只用考虑数列中的最小值和最大值，其他值经过操作后也一定夹在两数中间。↵
↵
### 代码↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include<algorithm>↵
#include<iostream>↵
#include<vector>↵
using std::cin;↵
using std::cout;↵
using std::endl;↵
using std::vector;↵
typedef long long ll;↵
const int N=200010;↵
int a[N],n;↵
int Ans[N],len;↵
void work(){↵
cin>>n;↵
len=0;↵
for(int i=1;i<=n;++i)↵
cin>>a[i];↵
std::sort(a+1,a+n+1);↵
ll x=a[1],y=a[n];//仅最小值与最大值就可以了↵
if(n==1)↵
cout<<0<<endl;↵
else{↵
while(x!=y){↵
if((x&1)==1&&(y&1)==0){//x 奇数 && y 偶数, +1 /2↵
Ans[++len]=1;↵
x=(x+1)>>1;↵
y=(y+1)>>1;↵
}↵
else{//其他, +0 /2↵
Ans[++len]=0;↵
x>>=1;↵
y>>=1;↵
}↵
}↵
cout<<len<<endl;↵
if(len<=n){↵
for(int i=1;i<=len;++i)↵
cout<<Ans[i]<<' ';↵
cout<<endl;↵
}↵
}↵
}↵
signed main(int argc,char **argv){↵
// freopen("order.in","r",stdin);↵
// freopen("order.out","w",stdout);↵
cin.tie(nullptr)->sync_with_stdio(false);↵
int T;↵
cin>>T;↵
while(T--)↵
work();↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
## D. Yet Another Monster Fight↵
↵
### 简要翻译↵
↵
有 $n$ 个怪兽，第 $i$ 个的生命值为 $a_i$。↵
↵
Vasya 有闪电法术，他可以选择初始威力 $x$ 和攻击的第一个怪兽 $i_1$。↵
↵
每次攻击后，闪电会随机攻击一个尚未被攻击且旁边有被攻击过怪兽的怪兽。↵
↵
第 $k$ 次攻击的怪兽 $i_k$ 收到 $(x-k+1)$ 点伤害，这个值大于等于 $a_i$ 会使怪兽死亡。↵
↵
现在 Vasya 想确定最小的 $x$，使得在适当挑选 $i_1$ 后，无论闪电的攻击顺序如何，所有怪兽都会死亡。↵
↵
### 思路解析↵
↵
对于 $a_i$，考虑 $i_1<i$ 和 $i_1>i$ 的情况。↵
↵
1. $i_1<i$：$a_i$ 能影响 $x$ 取值的最坏情况是，把前 $i-1$ 个数都消灭之后再消灭 $a_i$，对应的 $x$ 至少为 $a_i+i-1$。↵
2. $i_1>i$：最坏情况变为，把后面 $a_{i+1} \sim a_n$ 都消灭后再消灭 $a_i$，对应的 $x$ 至少为 $a_i+n-i$。↵
↵
第一种情况求后缀，第二种情况求前缀（$\max$），然后 $i_1=i$ 时的答案为 $\max \lbrace pre_{i-1}, a_i, nxt_{i+1} \rbrace $，取最小值即可。↵
↵
### 代码↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include<algorithm>↵
#include<iostream>↵
#include<vector>↵
using std::cin;↵
using std::cout;↵
using std::endl;↵
using std::max;↵
typedef long long ll;↵
const int N=300010;↵
ll a[N],pre[N],nxt[N],n;↵
void work(){↵
cin>>n;↵
for(int i=1;i<=n;++i)↵
cin>>a[i];↵
for(int i=1;i<=n;++i)↵
pre[i]=a[i]+n-i,// i1 > i↵
nxt[i]=a[i]+i-1;// i1 < i↵
ll ans=0x3f3f3f3f3f3f3f3f;↵
for(int i=2;i<=n;++i)↵
pre[i]=max(pre[i],pre[i-1]);↵
for(int i=n-1;i;--i)↵
nxt[i]=max(nxt[i],nxt[i+1]);↵
nxt[n+1]=pre[0]=0;↵
for(int i=1;i<=n;++i)↵
ans=std::min(ans,max(a[i],max(pre[i-1],nxt[i+1])));↵
cout<<ans<<endl;↵
}↵
signed main(int argc,char **argv){↵
// freopen("order.in","r",stdin);↵
// freopen("order.out","w",stdout);↵
cin.tie(nullptr)->sync_with_stdio(false);↵
int T=1;↵
while(T--)↵
work();↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
## E. Compressed Tree↵
↵
### 简要翻译↵
↵
有一棵 $n$ 个点的树，每个点有权值 $a_i$。↵
↵
在第一阶段，你可以选择任意一个有至多 $1$ 条边的点，并删除这个点和它所连的边。可以重复任意次。↵
↵
在第二阶段，所有度为 $2$ 的点将被删去，原来和它相连的 $2$ 个点之间生成一条新边。一直重复直到不存在度为 $2$ 的点。↵
↵
求压缩后剩下的点的权值和最大值。注意，权值可以是负数。↵
↵
### 思路分析↵
↵
比赛时想到树形 dp，但是想到换根去了，最后浪费一个小时。↵
↵
官方题解的说法，是按保不保留 $x$ 与父亲 $fa_x$ 的边，以及 $x$ 保留儿子的个数来讨论的。↵
↵
设 $f_x$ 为**保留**边 $(x,fa_x)$ 时，$x$ 及其子树内压缩后的最大权值和。↵
↵
则讨论 $x$ 保留儿子的个数：↵
↵
1. 不保留： 只保留 $x$ 作为叶子，$f_x =\max(f_x,a_x)$。↵
↵
2. 保留 $1$ 个：那么 $x$ 恰好有两条边，压缩后消失，$f_x=\max(f_x,\underset{y}{\max}f_y)$。↵
↵
3. 保留 $2$ 个及以上：$x$ 可以保留，$f_x=\max(f_x,a_x+\underset{y}{\sum}\max(0,f_y))$，至少选两个 $f_y$。↵
↵
考虑**不保留**边 $(x,fa_x)$ 时，$x$ 子树外的节点全部都被删除了。↵
↵
再讨论保留儿子的个数：↵
↵
1. 不保留：$ans=\max(ans,a_x)$。↵
↵
2. 保留 $1$ 个：$ans=\max(ans,a_x+\underset{y}{max}f_y)$。↵
↵
3. 保留 $2$ 个：$x$ 恰好会被压缩，$ans=\max(ans,\underset{y_1,y_2}{\max}(f_{y_1}+f_{y_2}))$。↵
↵
4. 保留 $3$ 个及以上：$ans=\max(ans,\underset{y}{\sum}\max(0,f_y))$，至少选三个 $f_y$。↵
↵
儿子个数用类似 $01$ 背包的写法，非常巧妙。↵
↵
### 代码↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include<algorithm>↵
#include<iostream>↵
#include<vector>↵
using std::cin;↵
using std::cout;↵
using std::endl;↵
using std::vector;↵
using std::max;↵
typedef long long ll;↵
const ll inf=0x3f3f3f3f3f3f3f3f;↵
const int N=500010;↵
↵
vector<int> ver[N];↵
ll val[N];↵
ll f[N],ans;↵
int n;↵
void clear(){↵
for(int i=1;i<=n;++i)↵
ver[i].clear();↵
ans=0;↵
}↵
void dfs(int x,int fa){↵
vector<ll> sum(4, -inf);↵
sum[0]=0;↵
for(int y : ver[x]){↵
if(y==fa)continue;↵
dfs(y,x);↵
sum[3]=max(sum[3],sum[3]+f[y]);//更新 f[y] 的和↵
for(int j=3;j;--j)// 更新选 1/2 个时 f[y] 的最优值↵
sum[j]=max(sum[j],sum[j-1]+f[y]);↵
}↵
f[x]=-inf;↵
for(int j=0;j<4;++j)↵
f[x]=max(f[x],sum[j]+(j==1?0:val[x])),↵
ans=max(ans,sum[j]+(j==2?0:val[x]));↵
}↵
void work(){↵
cin>>n;↵
clear();↵
for(int i=1;i<=n;++i)↵
cin>>val[i];↵
for(int i=1,x,y;i<n;++i){↵
cin>>x>>y;↵
ver[x].push_back(y);↵
ver[y].push_back(x);↵
}↵
dfs(1,0);↵
cout<<ans<<endl;↵
}↵
signed main(int argc,char **argv){↵
// freopen("order.in","r",stdin);↵
// freopen("order.out","w",stdout);↵
cin.tie(nullptr)->sync_with_stdio(false);↵
int T;↵
cin>>T;↵
while(T--)↵
work();↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
### F. Landscaping↵
↵
### 简要翻译↵
↵
没看懂呢↵
↵
### 思路分析↵
↵
没想出来呢↵
↵
### 代码↵
↵
没写呢
↵
比赛链接 [contest:1901]↵
↵
目前进度：↵
↵
| A | B | C | D | E | F |↵
| :------------: | :------------: | :------------: | :------------: | :----------: | :--------: |↵
| solved contest | solved contest | solved contest | solved contest | solved later | not solved |↵
↵
↵
↵
## A. Line Trip↵
↵
### 简要翻译↵
↵
在一维数轴上，有一辆车，刚开始在 $0$ 且油箱为满，走一个单位消耗一升油，经过 $a_1,a_2\ldots a_n$ 处可加满油。↵
↵
现在需要从 $0$ 走到 $x$ 再走回 $0$，求能完成路径的油箱油量最小值。↵
↵
### 思路解析↵
↵
先不考虑回程，设 $a_0=0$，则 $ans = \underset{1\le i\le n}{max} \lbrace a_{i}-a_{i-1} \rbrace$。↵
↵
在 $x$ 处转弯时不能加油，所以有 $ans = max(ans,2(x-a_n))$。↵
↵
返程和去程一样，不用再统计。↵
↵
↵
~~~~~↵
#include<algorithm>↵
#include<iostream>↵
const int N=100;↵
int a[N],n,x;↵
void work(){↵
std::cin>>n>>x;↵
for(int i=1;i<=n;++i)↵
std::cin>>a[i];↵
int ans=2*(x-a[n]);↵
for(int i=1;i<=n;++i)↵
ans=std::max(ans,a[i]-a[i-1]);↵
std::cout<<ans<<std::endl;↵
}↵
signed main(int argc,char **argv){↵
// freopen("order.in","r",stdin);↵
// freopen("order.out","w",stdout);↵
std::cin.tie(nullptr)->sync_with_stdio(false);↵
int T;↵
std::cin>>T;↵
while(T--)↵
work();↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
## B. Chip and Ribbon↵
↵
### 简要翻译↵
↵
有一列 $n$ 个格子和一个指针，一开始格子里的数 $a_i=0$ 。↵
↵
第 $1$ 步，Mococarp 会把指针放在第一个格子上，接下来每一步可以做下列两种移动之一：↵
↵
1. 若指针在第 $i$ 个格子上，且 $i \neq n$，则将指针放在 $i+1$ 上。↵
↵
2. 将指针放在任意一个格子上（可以放在同一个格子上）。↵
↵
每一步之后，若指针在第 $x$ 个格子上，则 $a_x$ 加一。↵
↵
现在，Mococarp 想尽可能少的使用移动 $2$，使得 $\forall i\in [1,n],a_i=c_i$。↵
↵
### 思路解析↵
↵
只使用移动 $1$ 时相当于给一个区间加一，问题转化为用多少个区间可以使 $i$ 被 $c_i$ 个区间包含。↵
↵
那么 $c_i>c_{i-1}$ 时表示有 $c_i -c_{i-1}$ 个区间要从 $i$ 开始，$ans+=c_i-c_{i-1}$。↵
↵
↵
~~~~~↵
#include<algorithm>↵
#include<iostream>↵
#include<vector>↵
using std::cin;↵
using std::cout;↵
using std::endl;↵
using std::vector;↵
typedef long long ll;↵
const int N = 200010;↵
ll c[N],n;↵
void work(){↵
cin>>n;↵
for(int i=1;i<=n;++i)↵
cin>>c[i];↵
ll ans=0;↵
for(int i=1;i<=n;++i)↵
if(c[i]>c[i-1])↵
ans+=c[i]-c[i-1];↵
cout<<ans-1<<endl;↵
}↵
signed main(int argc,char **argv){↵
// freopen("order.in","r",stdin);↵
// freopen("order.out","w",stdout);↵
cin.tie(nullptr)->sync_with_stdio(false);↵
int T;↵
cin>>T;↵
while(T--)↵
work();↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
## C. Add, Divide and Floor↵
↵
### 简要翻译↵
↵
有一个数组 $\lbrace a_n \rbrace$，每次可以选一个 $x$，将所有 $a_i$ 赋值为 $\lfloor \dfrac{a_i+x}{2} \rfloor$，求最少次数使 $a_1=a_2=\cdots=a_n$。↵
↵
### 思路解析↵
↵
先考虑两个数 $x,y(x<y)$ 如何化为相等值。↵
↵
考虑两者的差值，若选的数 $v \ge 2$ 则总有等效操作。↵
↵
如果 $v\ge 2$ 且为偶数，则 $\lfloor \dfrac{x+v}{2} \rfloor = \lfloor \dfrac{x}{2} \rfloor+\dfrac{v}{2}$，$\lfloor \dfrac{y+v}{2} \rfloor = \lfloor \dfrac{y}{2} \rfloor+\dfrac{v}{2}$，和直接除以二的效果相同。↵
↵
如果 $v\ge 2$ 且为奇数，则和加一再除以二的效果相同。↵
↵
观察样例，在 $x$ 为奇数 且 $y$ 为偶数时，加一再除以二相当于除以二后只给 $x$ 加一。↵
↵
其他情况下，加一再除以二不如直接除以二。↵
↵
因为 $x\le y \Leftrightarrow \lfloor \dfrac{x+v}{2} \rfloor \le \lfloor \dfrac{y+v}{2} \rfloor$，所以只用考虑数列中的最小值和最大值，其他值经过操作后也一定夹在两数中间。↵
↵
↵
~~~~~↵
#include<algorithm>↵
#include<iostream>↵
#include<vector>↵
using std::cin;↵
using std::cout;↵
using std::endl;↵
using std::vector;↵
typedef long long ll;↵
const int N=200010;↵
int a[N],n;↵
int Ans[N],len;↵
void work(){↵
cin>>n;↵
len=0;↵
for(int i=1;i<=n;++i)↵
cin>>a[i];↵
std::sort(a+1,a+n+1);↵
ll x=a[1],y=a[n];//仅最小值与最大值就可以了↵
if(n==1)↵
cout<<0<<endl;↵
else{↵
while(x!=y){↵
if((x&1)==1&&(y&1)==0){//x 奇数 && y 偶数, +1 /2↵
Ans[++len]=1;↵
x=(x+1)>>1;↵
y=(y+1)>>1;↵
}↵
else{//其他, +0 /2↵
Ans[++len]=0;↵
x>>=1;↵
y>>=1;↵
}↵
}↵
cout<<len<<endl;↵
if(len<=n){↵
for(int i=1;i<=len;++i)↵
cout<<Ans[i]<<' ';↵
cout<<endl;↵
}↵
}↵
}↵
signed main(int argc,char **argv){↵
// freopen("order.in","r",stdin);↵
// freopen("order.out","w",stdout);↵
cin.tie(nullptr)->sync_with_stdio(false);↵
int T;↵
cin>>T;↵
while(T--)↵
work();↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
## D. Yet Another Monster Fight↵
↵
### 简要翻译↵
↵
有 $n$ 个怪兽，第 $i$ 个的生命值为 $a_i$。↵
↵
Vasya 有闪电法术，他可以选择初始威力 $x$ 和攻击的第一个怪兽 $i_1$。↵
↵
每次攻击后，闪电会随机攻击一个尚未被攻击且旁边有被攻击过怪兽的怪兽。↵
↵
第 $k$ 次攻击的怪兽 $i_k$ 收到 $(x-k+1)$ 点伤害，这个值大于等于 $a_i$ 会使怪兽死亡。↵
↵
现在 Vasya 想确定最小的 $x$，使得在适当挑选 $i_1$ 后，无论闪电的攻击顺序如何，所有怪兽都会死亡。↵
↵
### 思路解析↵
↵
对于 $a_i$，考虑 $i_1<i$ 和 $i_1>i$ 的情况。↵
↵
1. $i_1<i$：$a_i$ 能影响 $x$ 取值的最坏情况是，把前 $i-1$ 个数都消灭之后再消灭 $a_i$，对应的 $x$ 至少为 $a_i+i-1$。↵
2. $i_1>i$：最坏情况变为，把后面 $a_{i+1} \sim a_n$ 都消灭后再消灭 $a_i$，对应的 $x$ 至少为 $a_i+n-i$。↵
↵
第一种情况求后缀，第二种情况求前缀（$\max$），然后 $i_1=i$ 时的答案为 $\max \lbrace pre_{i-1}, a_i, nxt_{i+1} \rbrace $，取最小值即可。↵
↵
↵
~~~~~↵
#include<algorithm>↵
#include<iostream>↵
#include<vector>↵
using std::cin;↵
using std::cout;↵
using std::endl;↵
using std::max;↵
typedef long long ll;↵
const int N=300010;↵
ll a[N],pre[N],nxt[N],n;↵
void work(){↵
cin>>n;↵
for(int i=1;i<=n;++i)↵
cin>>a[i];↵
for(int i=1;i<=n;++i)↵
pre[i]=a[i]+n-i,// i1 > i↵
nxt[i]=a[i]+i-1;// i1 < i↵
ll ans=0x3f3f3f3f3f3f3f3f;↵
for(int i=2;i<=n;++i)↵
pre[i]=max(pre[i],pre[i-1]);↵
for(int i=n-1;i;--i)↵
nxt[i]=max(nxt[i],nxt[i+1]);↵
nxt[n+1]=pre[0]=0;↵
for(int i=1;i<=n;++i)↵
ans=std::min(ans,max(a[i],max(pre[i-1],nxt[i+1])));↵
cout<<ans<<endl;↵
}↵
signed main(int argc,char **argv){↵
// freopen("order.in","r",stdin);↵
// freopen("order.out","w",stdout);↵
cin.tie(nullptr)->sync_with_stdio(false);↵
int T=1;↵
while(T--)↵
work();↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
## E. Compressed Tree↵
↵
### 简要翻译↵
↵
有一棵 $n$ 个点的树，每个点有权值 $a_i$。↵
↵
在第一阶段，你可以选择任意一个有至多 $1$ 条边的点，并删除这个点和它所连的边。可以重复任意次。↵
↵
在第二阶段，所有度为 $2$ 的点将被删去，原来和它相连的 $2$ 个点之间生成一条新边。一直重复直到不存在度为 $2$ 的点。↵
↵
求压缩后剩下的点的权值和最大值。注意，权值可以是负数。↵
↵
### 思路分析↵
↵
比赛时想到树形 dp，但是想到换根去了，最后浪费一个小时。↵
↵
官方题解的说法，是按保不保留 $x$ 与父亲 $fa_x$ 的边，以及 $x$ 保留儿子的个数来讨论的。↵
↵
设 $f_x$ 为**保留**边 $(x,fa_x)$ 时，$x$ 及其子树内压缩后的最大权值和。↵
↵
则讨论 $x$ 保留儿子的个数：↵
↵
1. 不保留： 只保留 $x$ 作为叶子，$f_x =\max(f_x,a_x)$。↵
↵
2. 保留 $1$ 个：那么 $x$ 恰好有两条边，压缩后消失，$f_x=\max(f_x,\underset{y}{\max}f_y)$。↵
↵
3. 保留 $2$ 个及以上：$x$ 可以保留，$f_x=\max(f_x,a_x+\underset{y}{\sum}\max(0,f_y))$，至少选两个 $f_y$。↵
↵
考虑**不保留**边 $(x,fa_x)$ 时，$x$ 子树外的节点全部都被删除了。↵
↵
再讨论保留儿子的个数：↵
↵
1. 不保留：$ans=\max(ans,a_x)$。↵
↵
2. 保留 $1$ 个：$ans=\max(ans,a_x+\underset{y}{max}f_y)$。↵
↵
3. 保留 $2$ 个：$x$ 恰好会被压缩，$ans=\max(ans,\underset{y_1,y_2}{\max}(f_{y_1}+f_{y_2}))$。↵
↵
4. 保留 $3$ 个及以上：$ans=\max(ans,\underset{y}{\sum}\max(0,f_y))$，至少选三个 $f_y$。↵
↵
儿子个数用类似 $01$ 背包的写法，非常巧妙。↵
↵
↵
~~~~~↵
#include<algorithm>↵
#include<iostream>↵
#include<vector>↵
using std::cin;↵
using std::cout;↵
using std::endl;↵
using std::vector;↵
using std::max;↵
typedef long long ll;↵
const ll inf=0x3f3f3f3f3f3f3f3f;↵
const int N=500010;↵
↵
vector<int> ver[N];↵
ll val[N];↵
ll f[N],ans;↵
int n;↵
void clear(){↵
for(int i=1;i<=n;++i)↵
ver[i].clear();↵
ans=0;↵
}↵
void dfs(int x,int fa){↵
vector<ll> sum(4, -inf);↵
sum[0]=0;↵
for(int y : ver[x]){↵
if(y==fa)continue;↵
dfs(y,x);↵
sum[3]=max(sum[3],sum[3]+f[y]);//更新 f[y] 的和↵
for(int j=3;j;--j)// 更新选 1/2 个时 f[y] 的最优值↵
sum[j]=max(sum[j],sum[j-1]+f[y]);↵
}↵
f[x]=-inf;↵
for(int j=0;j<4;++j)↵
f[x]=max(f[x],sum[j]+(j==1?0:val[x])),↵
ans=max(ans,sum[j]+(j==2?0:val[x]));↵
}↵
void work(){↵
cin>>n;↵
clear();↵
for(int i=1;i<=n;++i)↵
cin>>val[i];↵
for(int i=1,x,y;i<n;++i){↵
cin>>x>>y;↵
ver[x].push_back(y);↵
ver[y].push_back(x);↵
}↵
dfs(1,0);↵
cout<<ans<<endl;↵
}↵
signed main(int argc,char **argv){↵
// freopen("order.in","r",stdin);↵
// freopen("order.out","w",stdout);↵
cin.tie(nullptr)->sync_with_stdio(false);↵
int T;↵
cin>>T;↵
while(T--)↵
work();↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
### F. Landscaping↵
↵
### 简要翻译↵
↵
没看懂呢↵
↵
### 思路分析↵
↵
没想出来呢↵
↵
### 代码↵
↵
没写呢
